home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / graphic / rtnews.zip / RTNV3N4 < prev    next >
Text File  |  1992-09-13  |  114KB  |  2,662 lines

  1.  _ __                 ______                         _ __
  2. ' )  )                  /                           ' )  )
  3.  /--' __.  __  ,     --/ __  __.  _. o ____  _,      /  / _  , , , _
  4. /  \_(_/|_/ (_/_    (_/ / (_(_/|_(__<_/ / <_(_)_    /  (_</_(_(_/_/_)_
  5.          /                               /|
  6.         '                               |/
  7.  
  8.             "Light Makes Right"
  9.  
  10.               October 1, 1990
  11.             Volume 3, Number 4
  12.  
  13. Compiled by Eric Haines, 3D/Eye Inc, 2359 Triphammer Rd, Ithaca, NY 14850
  14.     wrath.cs.cornell.edu!eye!erich or erich@eye.com
  15. All contents are US copyright (c) 1990 by the individual authors
  16. Archive locations: anonymous FTP at cs.uoregon.edu [128.223.4.13], /pub/RTNews,
  17.            weedeater.math.yale.edu [130.132.23.17], /pub/RTNews, and
  18.            freedom.graphics.cornell.edu [128.84.247.85], /pub/RTNews.
  19. UUCP access: Vol 3, No 1 or write Kory Hamzeh (quad.com!avatar!kory) for info.
  20.  
  21. Contents:
  22.     Introduction
  23.     New People, Address Changes, etc
  24.     Photorealism, and the color Pink (TM), from Andrew Glassner
  25.     DKBTrace v2.0 and Ray Tracing BBS Announcement, by David Buck, Aaron Collins
  26.     Article Summaries from Eurographics Workshop, by Pete Shirley
  27.     Convex Polyhedron Intersection via Kay & Kajiya, by Eric Haines
  28.     New Radiosity Bibliography Available, by Eric Haines
  29.     A Suggestion for Speeding Up Shadow Testing Using Voxels, by Andrew Pearce
  30.     Real3d, passed on by Juhana Kouhia, "Zap" Andersson
  31.     Utah Raster Toolkit Patch, by Spencer Thomas
  32.     NFF Shell Database, by Thierry Leconte
  33.     FTP list update and New Software, by Eric Haines, George Kyriazis
  34.     ======== USENET cullings follow ========
  35.     Humorous Anecdotes, by J. Eric Townsend, Greg Richter, Michael McCool,
  36.     Eric Haines
  37.     Graphics Interface '91 CFP
  38.     Parametric Surface Reference, by Spencer Thomas
  39.     Solid Light Sources Reference, by Steve Hollasch, Philip Schneider
  40.     Graphics Gems Source Code Available, by Andrew Glassner, David Hook
  41.     Graphics Gems Volume 2 CFP, by Sari Kalin
  42.     Foley, Van Dam, Feiner and Hughes "Computer Graphics" Bug Reports,
  43.     by Steve Feiner
  44.     Radiosity via Ray Tracing, by Pete Shirley
  45.     Algorithm Order Discussion, by Masataka Ohta, Pete Shirley
  46.     Point in Polygon, One More Time..., by Mark Vandewettering, Eric Haines,
  47.     Edward John Kalenda, Richard Parent, Sam Uselton, "Zap" Andersson,
  48.     and Bruce Holloway
  49.     Quadrant Counting Polygon In/Out Testing, by Craig Kolb, Ken McElvain
  50.     Computer Graphics Journals, by Juhana Kouhia
  51.  
  52. -------------------------------------------------------------------------------
  53.  
  54. Introduction
  55.  
  56. Well, SIGGRAPH has come and gone, and as usual I ran out of time.  There's
  57. just too many people to meet and too much to see and do.  Highlights for me
  58. included the SIGGRAPH Trivia Bowl, meeting in a cemetery for lunch with other
  59. renderers after an all night session of Hurtenflurst (don't ask), and getting
  60. my head turned into data at Failure Analysis Associates (still haven't heard
  61. from them, though.  Does anyone have the phone number or address for this
  62. company?  I'd like to call and find out what is happening with them).  At
  63. SIGBowl our Ithaca team was able to lock in third place [of 3 teams] early on
  64. and held it against all comers.  Nonetheless, a great time:  one of many
  65. favorite moments was:
  66.  
  67.     Pike (the moderator): "Who's biographical sketch reads as follows-"
  68.  
  69.         BUZZ!
  70.  
  71.     Team 1 (with no other information): "Turner Whitted!?"
  72.  
  73.     Pike: "No, wrong.  Now let me read the question" and proceeds to read
  74.         some biographical data.
  75.  
  76.         BUZZ!
  77.  
  78.     Team 2: "Is it Turner Whitted!?"
  79.  
  80.     Pike: "Still wrong."
  81.  
  82. Team 3, sadly, did not guess "Turner Whitted?", but, rather, declined to answer.
  83.  
  84. --------
  85.  
  86. Does anyone have a nice, compact version of the Teapot?  That is, just the
  87. spline description (which I do have) and a tessellator which will turn it into
  88. quads/triangles (which I have, but it's deeply buried in some scary code)?
  89. This would be a nice addition to SPD 3.0, but I don't have one easily
  90. accessible.  Here's your chance to get your code distributed in the next
  91. release.  I'm willing to massage your code into outputting NFF format.
  92.  
  93. I'll also announce that there is a new version of the ray tracing bibliography
  94. which I've finished as of today.  Many of the new articles listed are due to
  95. the untiring work of Tom Wilson, who says the librarians now hate him.  This
  96. new version should be available via FTP by October 5th on
  97. freedom.graphics.cornell.edu and cs.uoregon.edu (see the FTP site list later
  98. in this issue for more information).
  99.  
  100. Important dates:
  101.     Graphics Interface papers due October 31st
  102.     Graphics Gems, Volume 2 submissions due November 1st
  103.  
  104. -------------------------------------------------------------------------------
  105.  
  106. New People, Address Changes, etc
  107.  
  108.  
  109. # Tom Wilson - parallel ray tracing, spatial subdivision
  110. # Center for Parallel Computation
  111. # Department of Computer Science (407-275-2341)
  112. # University of Central Florida
  113. # P.O. Box 25000
  114. # Orlando, FL 32816-0362
  115. alias    tom_wilson    wilson@ucf-cs.ucf.edu
  116.  
  117. I am a Ph.D. student at UCF.  I am working in the area of parallel processing
  118. with ray tracing as an application.  I am working on a nonuniform spatial
  119. subdivision scheme that will eventually be implemented on our BBN Butterfly
  120. GP1000.
  121.  
  122. --------
  123.  
  124. # Steve Hollasch - efficiency, algorithms, ray-tracing
  125. # Master's Student in C.S., Arizona State University
  126. # 1437 West 6th Street
  127. # Tempe, AZ  85281-3205
  128. # (602) 829-8758
  129. alias   steve_hollasch   hollasch@enuxha.eas.asu.edu
  130.  
  131.     I'm working on completing my thesis in December 1990 or January 1991.  The
  132. research basically covers viewing 4D objects (as physical entities, not 3D
  133. scalar fields).  I'm working on a 4D raytracer right now that handles
  134. hyperspheres and tetrahedrons, and I hope to extend it to hyperellipsoids,
  135. hypercones, hypercylinders and so on.  I'd also like to learn how to tessellate
  136. 4D solids with tetrahedrons to be able to view arbitrary 4D solids.  Practical
  137. uses?  I'm still trying to think off something...  =^)
  138.  
  139. --------
  140.  
  141. # Christophe Vedel - improving radiosity
  142. # LIENS, Ecole Normale Superieure
  143. # 45, rue d'Ulm
  144. # 75230 PARIS Cedex 05 FRANCE
  145. # (33) 1 43 26 59 74
  146. e-mail  vedel@ens.ens.fr
  147.     vedel@FRULM63.BITNET
  148.  
  149. I'm interested in improving the radiosity method for finer results or larger
  150. scenes.  Spatial subdivision techniques developed for ray tracing should help
  151. to achieve this goal.  I'm also working on interactivity with lighting
  152. simulation programs.
  153.  
  154. --------
  155.  
  156. # Frederic Asensio - behavioral animation, radiosity
  157. # LIENS, Ecole Normale Superieure
  158. # 45, rue d'Ulm
  159. # 75230 PARIS Cedex 05 FRANCE
  160. # (33) 1 43 26 59 74
  161. e-mail  asensio@ens.ens.fr
  162.     asensio@FRULM63.BITNET
  163.  
  164. I am interested in interactive radiosity methods, which could be used in the
  165. design process and in stochastic methods for light sampling with rays.
  166.  
  167. --------
  168.  
  169. # Scott Senften - efficiency, scientific visualization
  170. # McDonnell Douglas Corp.
  171. # McDonnell Aircraft Co.
  172. # Mail Code 1065485
  173. # St. Louis, MO 63166
  174. # (314)232-1604
  175. alias scott_senften      senften%d314vx.decnet@mdc.com
  176. alias senften_tu     senften@tusun2.utulsa.edu
  177.  
  178. Presently I'm doing research in neural nets.  There is a real need in the NN
  179. society for some good scientific visualization.  I'm presently doing work in
  180. speech recognition, diagnostics, flight reconfiguration, and signal
  181. processing, as well as graphic visualization of neural networks.  My graduate
  182. work was in Ray Tracing efficiency.
  183.  
  184. --------
  185.  
  186. Sam Uselton
  187.  
  188. Internet:
  189. uselton@nas.nasa.gov
  190.  
  191.     Work             Home
  192. Phone:
  193. (415) 604-3985               (415) 651-6504
  194.  
  195. USMail:
  196. Samuel P. Uselton, PhD           Sam Uselton
  197. Computer Sciences Corp.
  198. M/S T 045-1               1216 Austin St.
  199. NASA Ames Research Center      Fremont, CA 94539
  200. Moffett Field, CA 94035
  201.  
  202.  
  203. Ray Tracing interests:
  204. efficiency, accuracy, distributed ray tracing, parallel implementations
  205.  
  206.  
  207. At NASA I'm working on volume visualization for computational fluid dynamics.
  208. I've used this as an excuse ( :-) ) to write a ray caster (no bounces) that
  209. integrates through the volume, accelerated by taking advantage of the special
  210. grids, as well as an item buffer-like initial hit finder.
  211.  
  212. I'm also working with Redner & Lee on extending our distributed ray tracing
  213. work to handle diffuse illumination, caustics, wavelength dependent
  214. refraction, and other realistic effects.
  215.  
  216. Once these problems are completely solved ( :-) :-) ), there are several
  217. parallel machines here that I would like to wring out.
  218.  
  219. Oh yes, we (Lee, Steve Stepoway, Scott Senften and myself) have yet another
  220. Acceleration technique we like better than any of the popular ones.  (Actually
  221. it can combine with bounding boxes.)  It is somewhere between regular space
  222. subdivision (a la medical volume folks and Japanese SEADS..)  and the bounding
  223. slabs idea (Kaplan?  [no, Kay]).  It was written and submitted for pub once,
  224. but we keep thinking of new tweaks, so it is being re-written.
  225.  
  226. --------
  227.  
  228. # Juhana Kouhia
  229. # Ylioppilaankatu 10 C 15
  230. # 33720 Tampere
  231. # Finland
  232. alias    juhana_kouhia    jk87377@tut.fi
  233.  
  234. I have done my wireframe, scanline and ray tracing programs with Jim Blinn's
  235. modeling language.
  236.  
  237. [Another renderer with a last name starting with K!  There's Kajiya, Kaplan,
  238. Kay, Kirk, Kolb, Kuchkuda, Kyriazis, just to mention a few. --EAH]
  239.  
  240. --------
  241.  
  242. # Michael L. Kaufman  - speed, ray tracing on a PC, ray tracing fractal images
  243. # Northwestern University
  244. # 2247 Ridge Ave #2k
  245. # Evanston IL, 60201
  246. # (708) 864- 7916
  247. # kaufman@eecs.nwu.edu
  248.  
  249. I am just getting started in Ray-Tracing.  I am interested in coming up with
  250. algorithms that are fast enough to do on a 386 PC.  I am also interested in
  251. using Ray-Tracing techniques as a new way of looking at certain types of
  252. fractal images.
  253.  
  254. --------
  255.  
  256. Stephen Boyd Gowing - light transmission, motion, art
  257. B.App.Sc (Computing) Undergraduate.
  258. University of Technology, Sydney
  259.  
  260. 4/10 Short St, Glebe 2037 AUSTRALIA (home)
  261.  
  262. alias    stephen_gowing    sbgowing@ultima.cs.uts.oz.au
  263.  
  264. I'm currently half way through a project to study the effect of light passing
  265. through sphere(s).  The eventual aim is to produce a short animation showing a
  266. single sphere inverting an image which breaks (unmerges?)  into two spheres
  267. one behind the other and study the "flow" of the image through them.  At the
  268. moment I am still rewriting the tracer I used for my 2nd-last graphics
  269. assignment last year.  I'd like to do it in C++ but this would make things
  270. awkward as we don't have access to a compiler.  I'd also like to implement
  271. some sort of shading language into the image description - probably using
  272. something like forth.
  273.  
  274. --------
  275.  
  276. # Rick Brownrigg  --  efficiency, texturing, visualization, DTM displays
  277. # Kansas Geological Survey
  278. # University of Kansas
  279. # 1930 Constant Avenue
  280. # Lawrence, KS  USA  66046
  281. # 913 864 4991
  282.  
  283. -------------------------------------------------------------------------------
  284.  
  285. Mail, from Andrew Woo, George Kyriazis, Zap Andersson
  286.  
  287.  
  288. from Andrew Woo:
  289.  
  290. I have gone through many changes in the last year, from graduating with a
  291. M.Sc. at University of Toronto, to working at SAS Institute, to working at
  292. Alias Research - which is my current working address.  My e-mail at Alias is
  293. awoo@alias.UUCP.
  294.  
  295. I checked out your latest RT News.  I think David Jevans was a little too hard
  296. on you about not knowing about the ray id for voxel traversal.  In fact, in GI
  297. 90, one of the authors was unaware of it, too (in the "Approximate Ray
  298. Tracing" paper).  So you are not alone.  In fact, there is an explicit
  299. mentioning of ray id in an early paper that David did not mention:
  300.  
  301.     John Amanatides, "A Fast Voxel Traversal Algorithm for Ray Tracing",
  302.     EuroGraphics, 1987, pp. 1-10.
  303.  
  304. On the claim that David Jevans made about wasting time on more intersection
  305. culling schemes, I tend to agree.  In fact, I have stopped looking for more
  306. clever ways to cull intersections.  But I intend to check out another route to
  307. ray tracing savings.  Once I get some promising results, I will share the idea
  308. with you (to avoid any embarrassments in case the idea backfires).
  309.  
  310. On renaming DIstributed Ray Tracing, I am more of a fan of coming up with
  311. amusing acronyms for the algorithms.  For Cook's, I thought DiRT might be
  312. interesting.  I also came up with an acronym for my paper in GI 90 - Voxel
  313. Occlusion Method as an Intersection-culling Technique, which spells VOMIT.
  314.  
  315. --------
  316.  
  317. from George Kyriazis:
  318.  
  319. I was reading the last RTN issue I received.  In there it states about a
  320. program that converts sculpt4d to NFF, and it also commented that Sculpt4D is
  321. an exceptional modeler.  Well, I have my doubts.  Last spring I was working on
  322. a program to raytrace Scultpt4D files and animations on a Pixel Machine.
  323. Well, the file format is far from being strait-forward.  We had to call Byte
  324. by Byte for a few questions and stayed on the phone for more than an hour.
  325. One of the Sculpt4D unwanted 'features' was that it normalized the intensity
  326. of all displayed pixels wrt the brightest.  The result on the Pixel Machine
  327. was disastrous!  Images were either overexposed or totally black!  :-) Well,
  328. this is one of the problems faced, but I don't want to list more...
  329.  
  330. -------------------------------------------------------------------------------
  331.  
  332. Photorealism, and the color Pink (TM), from Andrew Glassner
  333.  
  334. From a Tektronix ad in this month's Advanced Imaging, we learn that it is now
  335. possible to turn real photographs into photorealistic images (presumably
  336. thereby increasing realism):
  337.  
  338. "Traditional workstations can't handle reality.  They create a simulated
  339. world...  With Dynamic Visualization, reality and simulation are brought
  340. together by TekImaging (TM), powerful image-processing software...  [and now,
  341. the big one -ag] TekImaging lets you transform real-world images into
  342. photo-realistic scenes, complete with light, shadow, and texture."
  343.  
  344. So now I can take a picture of myself, and using their software make it look
  345. photo-realistic and indistinguishable from a real picture - what a
  346. breakthrough!
  347.  
  348. --------
  349.  
  350. Beware of the colors you pick for your images.  Here's a footnote in an
  351. Owens-Corning Fiberglas ad in this month's [August?] Popular Science (pg 21):
  352.  
  353. "* The color Pink is a trademark of Owens-Corning Fiberglas Corp."
  354.  
  355. I think I'll get a trademark on red before all the good colors are taken...
  356.  
  357. -------------------------------------------------------------------------------
  358.  
  359. DKBTrace v2.0 and Ray Tracing BBS Announcement, by David Buck, Aaron Collins
  360.  
  361. I recently completed version 2.0 of my freely distributable raytracer called
  362. DKBTrace.  This raytracer is a project I've been working on (actually, off and
  363. on) for the past five years.  The raytracer features:
  364.  
  365.    - primitives for spheres, planes, triangles, and quadrics
  366.    - constructive solid geometry
  367.    - solid texturing using a Perlin-style noise function
  368.    - image mapping (IFF and GIF formats)
  369.    - hierarchical bounding boxes
  370.    - transparency
  371.    - fog
  372.    - 24 bit output files
  373.    - adaptive anti-aliasing using jittered supersampling
  374.    - "quick" previewing options
  375.  
  376. The raytracer was developed on an Amiga computer, but it is easily portable to
  377. other platforms.  The interface to the raytracer raytracer is a scripting
  378. language (sorry, no GUI).  The language is quite readable compared to many
  379. other input file formats.
  380.  
  381. The source and Amiga executables are available by anonymous FTP from
  382. alfred.ccs.carleton.ca [134.117.1.1].  The source and executables are freely
  383. distributable.
  384.  
  385. As with any raytracer, there are still things that need to be done, added, or
  386. improved with DKBTrace.  The image mapping was added at the last minute, so it
  387. only uses a simple projection scheme.  This means that the mappings look
  388. bizarre when viewed from the sides or the back.  For the most part, however,
  389. the solid textures are quite powerful and can create some very interesting
  390. effects.
  391.  
  392. To implement transparency, I decided to add the transparency value value to
  393. the color structure.  A color contains red, green, blue, and alpha components.
  394. This makes it much easier to use in textures.
  395.  
  396. The textures also allow you to define your own color map and to have the
  397. colors automatically interpolated from one range to the next.  Interpolating
  398. the colours makes the images look much better than just a simple step
  399. function.
  400.  
  401. Questions and comments concerning the raytracer can be directed to
  402. David_Buck@Carleton.CA on BITNET.  The IBM port (and several enhancements)
  403. were done by Aaron Collins.  Aaron can be reached on Compuserve.
  404.  
  405. --------
  406.  
  407. DKBtrace dox info:
  408.  
  409. Aaron Collins can be reached on the following BBS'es
  410.  
  411. Lattice BBS              (708) 916-1200
  412. The Information Exchange BBS  (708) 945-5575
  413. Stillwaters BBS              (708) 403-2826
  414.  
  415. AAC:  As of July of 1990, there will be a Ray-Trace specific BBS in the (708)
  416. Area Code (Chicago suburbia) for all you Traceaholics out there.  The phone
  417. number of this new BBS is (708) 358-5611.  I will be Co-Sysop of that board.
  418. There is also a new Ray-Trace and Computer-Generated Art specific SIG on
  419. Compuserve, GO COMART.  And now, back to the DOCS...
  420.  
  421. -------------------------------------------------------------------------------
  422.  
  423. Article Summaries from Eurographics Workshop, by Pete Shirley
  424.     (shirley@iuvax.cs.indiana.edu)
  425.  
  426. [What follows are summaries of ray tracing related articles given during the
  427. Eurographics Workshop on Photosimulation, Realism and Physics in Computer
  428. Graphics in Rennes, France, June 1990. - EAH]
  429.  
  430. INCREMENTAL RAY TRACING by Murakami and Hirota (Fujitsu)
  431. A extension of Parameterized ray tracing that allowed moving some scene
  432. objects in addition to changing material properties.  Used tables of
  433. changed voxels to determine if a ray's interaction with geometry has
  434. changed.  Included implementation on multiple CPUs.  Also includes
  435. reference to a paper in Japanese by Matsumoto on Octree ray tracing in
  436. 1983!
  437.  
  438. PARAMETRIC SURFACES AND RAY TRACING by Luc Biard (IMAG, France)
  439. Like most parametric patch papers, this one went over my head, but
  440. it seems to be an interesting paper, and includes some implementation results.
  441.  
  442. A PROGRESSIVE RAY TRACING BASED RADIOSITY WITH GENERAL REFLECTANCE FUNCTIONS
  443. by Le Saec and Schlick (France)
  444. A proposal for general BRDF radiosity (very similar to what I propose in the
  445. paper above).  Also includes method for interactive display - display only
  446. non-mirrors until viewer stops, then ray trace (UNC style).
  447.  
  448. LIGHT SOURCES IN A RAY TRACING ENVIRONMENT by Roelens et al. (France)
  449. A method for showing 'cone of light' effect when there is not very
  450. dense participating media in a room (primary scattering only).
  451.  
  452. METHODS FOR EFFICIENT SAMPLING OF ARBITRARILY DISTRIBUTED VOLUME DENSITIES
  453. by Hass and Sakas (FRG)
  454. Methods of sampling a volume density along a ray.
  455.  
  456. -------------------------------------------------------------------------------
  457.  
  458. Convex Polyhedron Intersection via Kay & Kajiya, by Eric Haines
  459.  
  460. I like Kay and Kajiya's bounding slabs method [SIGGRAPH 86] a lot.  By
  461. thinking about how this algorithm actually works, we can derive a method for
  462. intersecting convex polyhedra.  A working definition of a convex polyhedron is
  463. a polyhedron which can have at most two intersection points for any ray.
  464.  
  465. To review:
  466. Their idea is to form a bounding volume around an object by making slabs.  A
  467. slab is the volume between two parallel planes.  The intersection of all slabs
  468. is the bounding volume (i.e. the volume which is inside all slabs).  The
  469. intersection method works by intersecting each slab and checking out
  470. intersection conditions for it alone, then comparing these results to the
  471. answer for previous slabs.  That is, first we get the near and far
  472. intersection points for the ray with the slab.  If the far hit is behind the
  473. ray's origin (i.e. negative distance) or the near hit is beyond the maximum
  474. distance (i.e. you might limit how far the ray can travel by keeping track of
  475. the closest object hit so far, or the distance to the light if this is a
  476. shadow ray), then the ray cannot hit the bounding volume.
  477.  
  478. If the near and far hits are within bounds, then we essentially do a set
  479. operation of this line segment and any previous slab line segments formed.
  480. For example, if this is the second slab tested, we try to find the overlap of
  481. the first slab's hits and this slab's hits.  If the two segments do not
  482. overlap, then there is no point along the ray that is inside both slabs.  In
  483. other words, there is no point inside the bounding volume, since this volume
  484. is the logical intersection of all slabs.  To get the logical intersection of
  485. the slab segments, we merely store the largest of the near hits and the
  486. smallest of the far hits.  If this largest near hit is greater than this
  487. smallest far hit, there was no overlap between segments, so the bounding
  488. volume is missed.  If near is less than far, this new high-near, low-far
  489. segment is used against successive slab segments.  If the ray survives all
  490. segment tests, then the resulting near and far values are the distance along
  491. the ray of the near and far hits on the bounding volume itself.
  492.  
  493. What's interesting about this test is that it is essentially doing
  494. Constructive Solid Geometry operations between slabs, similar to [Roth 82].
  495. This simple idea can be extended further, allowing you to quickly intersect
  496. convex polyhedra.  Another good feature is that the polyhedra can be defined
  497. entirely by the plane equations for the faces, so no vertices have to be
  498. stored.
  499.  
  500. Imagine that you have defined a convex polyhedron by specifying each face
  501. using a plane equation, Ax + By + Cz + D = 0.  Have each face's normal {A,B,C}
  502. point outwards.
  503.  
  504. To intersect this object with a ray, simply test the ray against each face:
  505. if you hit a plane that faces towards the ray (i.e. the dot product of the
  506. normal and the ray direction is negative), then use this as a hit for near;
  507. if you hit a plane facing away, then use this as a hit for far.   Now, instead
  508. of having a line segment for each slab, you have an unbounded ray for each
  509. plane.  For example, if you have a hit for a near distance (i.e. you hit a
  510. forward facing plane), then you would first check if this near is beyond your
  511. current maximum distance.  If not, then you would store the maximum of this
  512. near value and the previous (if any) near value.  If at this point the stored
  513. near value is greater than the stored far value, the ray has missed.  This
  514. process continues with each plane until you miss or you run out of planes.
  515. The near and far points are then your intersection points with the polyhedron.
  516.  
  517. Essentially, this process is an extension of Kay & Kajiya: the ray is tested
  518. against each face and the intersection point is used to form a segment which
  519. is unbounded (infinite) on one end.  This segment is tested for validity
  520. against the ray's segment and the polyhedron's current intersection segment.
  521. If the polyhedron's segment is valid at the end of the process, then the ray
  522. hit the polyhedron.  Basically, each face of the polyhedron defines a
  523. half-space in which the inside of the polyhedron must lay.  The intersection of
  524. these half-spaces is the polyhedron itself.
  525.  
  526. One minor problem is what happens when the ray is parallel to the plane.  You
  527. could use Kay & Kajiya's suggestion of using some epsilon for the divisor,
  528. but I prefer handling this special case separately.  If parallel, then we
  529. want to check if the ray origin is inside the half-space:  if it is not, then
  530. the ray cannot ever hit the polyhedron (since the ray does not cross into the
  531. volume of valid intersections formed by this half-space).  In other words, if
  532. we substitute the origin into the plane equation, the result of the expression
  533. must be negative for the point to be inside the half-space; if not, the ray
  534. must miss the polyhedron.
  535.  
  536. The pseudo-code:
  537.  
  538.     Maxdist = maximum distance allowed along ray
  539.     Tnear = -MAXFLOAT, Tfar = MAXFLOAT
  540.     For each plane in the polyhedron:
  541.     Compute intersection point T and sidedness
  542.     dp = ray.direction DOT plane.normal
  543.     do = (ray.origin DOT plane.normal) - plane.d
  544.     If ( dp == 0 )
  545.         /* ray is parallel to plane - check if ray origin is inside plane's
  546.            half-space */
  547.         If ( do > 0 )
  548.         /* ray is outside half-space */
  549.         return MISSED
  550.     Else
  551.         /* ray not parallel */
  552.         T = do / dp
  553.         If ( dp < 0 )
  554.         /* front face - T is a near point */
  555.         If ( T > Maxdist ) return MISSED
  556.         If ( T > Tnear )
  557.             Tnear = T
  558.             Normal = plane.normal
  559.         Else
  560.         /* back face - T is a far point */
  561.         If ( T < 0.0 ) return MISSED
  562.         If ( T < Tfar ) Tfar = T
  563.         If ( Tnear > Tfar ) return MISSED
  564.     endfor
  565.     return HIT
  566.  
  567. At the end, Tnear is the intersection distance and Normal is the surface
  568. normal.  Tfar is the exit distance, if needed.
  569.  
  570. That's it:  instead of laborious inside/outside testing of the polygon on each
  571. face (and storing all those vertices), we have a quick plane test for each
  572. face.  If the number of planes is large, it might have been better to store
  573. the polygons and use an efficiency scheme.  However, the method above is
  574. certainly simpler to code up and is pretty efficient, compact, and robust:
  575. for example, there are no special edge intersection conditions, as there are
  576. no edges!
  577.  
  578. An aside:
  579. One thing that I hadn't mentioned is how we can better initialize the near and
  580. far hit distances before the slab tests.  It turns out that when testing
  581. bounding volumes we can set Tnear (the near distance) to 0 and Tfar to the
  582. maximum ray distance (if any - else set it to "infinity").  This corresponds
  583. to the segment formed by the ray:  we consider points between 0 and the
  584. maximum ray distance to be valid points on the ray, and so want to find slab
  585. segments that overlap this segment.  Note that these initial conditions gets
  586. rid of some complication for the algorithm:  we now don't have to test our
  587. slab segment against the ray's segment and the previous bounding volume
  588. segment, but rather are always testing against a single segment which
  589. represents the intersection of both of these.  This idea is not in Kay &
  590. Kajiya's presentation, by the way.
  591.  
  592. Note that there is one change that occurs if you initialize the near and far
  593. distances in this way:  the near and far distances computed when a volume is
  594. hit will not yield the true surface intersections, but rather will give the
  595. first and last points inside the volume.  This is useful for bounding volumes,
  596. since we usually just want to know if we hit them and have some idea of the
  597. distance.
  598.  
  599. -------------------------------------------------------------------------------
  600.  
  601. New Radiosity Bibliography Available, by Eric Haines
  602.  
  603. A bibliography of publications related to radiosity is now available at:
  604.  
  605.     freedom.graphics.cornell.edu [128.84.247.85]: /pub/Radiosity
  606.  
  607. It's a compressed package using "refer" format.  Articles related to radiosity
  608. or "non-classical" rendering (soft shadows, caustics, etc) are included here.
  609. This version is significantly improved from the version I posted some months
  610. ago.  Many thanks to all who helped update it.
  611.  
  612. -------------------------------------------------------------------------------
  613.  
  614. A Suggestion for Speeding Up Shadow Testing Using Voxels, by Andrew Pearce
  615.  
  616. Requirements:
  617. ------------
  618. This method is applicable to any type of spatial subdivision.  It is probably
  619. best suited to those of us who tessellate our objects to ray trace them.
  620.  
  621. Method:
  622. ------
  623. I've expanded on Eric Haines' method of storing the last object hit by a
  624. shadow ray with each light source, I now save a pointer to the voxel which
  625. contains the last object hit (or at least the voxel the intersection occurred
  626. in if the object spans multiple voxels).  My rationale is that if the shadow
  627. ray does NOT intersect the "last object" which shadowed that light source,
  628. then the likelihood of it hitting something in the neighborhood of that same
  629. object is pretty good.  If we save the voxel which the shadowing occurred in
  630. for the previous ray, we can examine the other objects in that voxel for
  631. possible light source occlusion WITHOUT the ray startup and voxel traversal
  632. costs.  Now this assumption is likely untrue if you're just tracing spheres
  633. and checker boards (some slight intended :^) but it works quite well for
  634. tessellated objects (NURBS patches in my case).
  635.  
  636. I NULL my pointers to both the last object and last voxel if no shadow
  637. intersection was found on the last shadow ray to this light.
  638.  
  639. I store a ray_id with every object to insure that any given ray is tested for
  640. intersection with an object ONLY ONCE even if it spans multiple voxels.  Each
  641. ray has a unique id.  (I thought, as did David Jevans, that this was a well
  642. known technique).  So, even if the shadow ray misses all of the objects in
  643. "last voxel" and must be traced like a regular shadow ray, we are likely not
  644. losing much since if the shadow ray enters the "last voxel" during it's
  645. traversal of the voxels, the ray will see that it has already been intersected
  646. with all of the objects in that voxel, and that voxel will be skipped
  647. relatively quickly (slightly slower than an empty voxel; the time it takes to
  648. compare the ray ID against the ray ID stored with each object).
  649.  
  650. Pseudo-code:
  651. -----------
  652. /****************************************************************************/
  653. /* Obviously we cannot use the "last object hit" for transparent        */
  654. /* objects since multiple objects may be involved in the shadowing process. */
  655. /* The code outlined below assumes that we only store the "last object" and */
  656. /* "last voxel" for shadow rays generated from a primary ray intersection.  */
  657. /* What we really should have is a tree indicating what was hit at each     */
  658. /* level of recursion. Ie. What object shadowed the intersection point      */
  659. /* generated by the last refraction ray, generated from a reflection ray    */
  660. /* generated by a primary ray?                            */
  661. /****************************************************************************/
  662. float check_shadowing(ray, light)
  663. RAY_REC   ray;   /* ray from shading point to light source */
  664. LIGHT_REC light; /* the light source we are interested in */
  665. {
  666. if (light.last_object != NULL) {
  667.  
  668.     /* intersect_object() marks object as having been */
  669.     /* intersected by this ray. */
  670.     hit = intersect_object( ray, light.last_object, &object);
  671.  
  672.     if (hit) {
  673.         return(1.0); /* full shadowing */
  674.     }
  675.  
  676.     if (light.last_voxel != NULL) { /* implied !hit */
  677.  
  678.         /* intersect_object_in_voxel_for_shadows() returns hit = TRUE */
  679.         /* on first affirmed intersection with a non-transparent
  680.          * object. */
  681.         /* It ignores transparent objects altogether. */
  682.         hit = intersect_objects_in_voxel_for_shadows( ray,
  683.                                   light.last_voxel,
  684.                                   &object);
  685.         if (hit) {
  686.             light.last_object = object;
  687.             return(1.0);
  688.         }
  689.     }
  690. }
  691.  
  692. /* traverse_voxels_for_shadows() DOES intersect transparent objects and */
  693. /* sorts the intersections for proper attenuation of the light intensity. */
  694. /* If it hits multiple objects, the object returned is the transparent one. */
  695. hit = traverse_voxels_for_shadows(ray, &object, &voxel, &shadow_percent);
  696.  
  697. if (!hit) {
  698.     light.last_object = light.last_voxel = NULL;
  699.     return(0.0);
  700. }
  701. if (object.transparency_value > 0.0) {
  702.     /* the object is transparent */
  703.     light.last_object = light.last_voxel = NULL;
  704. }
  705. else {
  706.     light.last_object = object;
  707.     light.last_voxel  = voxel;
  708. }
  709. return ( shadow_percent );
  710. }
  711.  
  712.  
  713. Results:
  714. -------
  715. (For the discussion below, "positive occlusion" means we have guaranteed that
  716. the point we are shading is shadowed from the light source.)
  717.  
  718. The "last object hit" method provided a positive occlusion 52% of the time,
  719. and if the "last object hit" method did not provide positive occlusion, the
  720. "last voxel" method provided a positive occlusion 76% of the time.
  721.  
  722. I performed a "pixie" of the code with and without this opt. on an SGI
  723. Personal Iris with no other code changes or scene changes, there is ONE light
  724. source in the scene which is casting shadows.  The ray tracer with the "last
  725. voxel" optimization used 2% fewer cycles.  (Actual system times vary wildly
  726. based on load, but the last voxel version did run about 10% faster using the
  727. UNIX "times()" system call, but I don't trust "times()").  Two percent
  728. doesn't seem like an awful lot, but this is just a quick and dirty hack, and I
  729. would expect to save 2% on EACH light source which casts shadows.
  730.  
  731. The test scene I'm using is a snare drum with a shadow casting spotlight on
  732. it.  See IEEE Computer Graphics & Applications, Sept.  1988, the cover story
  733. includes a tiny reproduction of the image should you wish to see what I'm
  734. playing with, although the image in CG&A was done with a 2D projective
  735. renderer (ray casting), not ray tracing.  The reflections in the floor and on
  736. the chrome in that image were realised using two separate cubic environment
  737. maps, the shadows were done with a depth map, the wallpaper is a simple
  738. parametric map and the floor boards have 6 separate solid wood textures
  739. randomly assigned to them.
  740.  
  741. The test scene contains approximately 60,000 triangles and I'm rendering at
  742. 512x512 resolution with no anti-aliasing, and a limit of one recursion level
  743. for both shadow and reflection rays for a total of 638,182 rays.  There is
  744. only one light in the scene which casts shadows.
  745.  
  746. I'll be doing tests on more scenes with various levels of voxel subdivision,
  747. and object distribution.  I'll let you know the results, even if they're
  748. negative!  (The above results did surprise me a little).
  749.  
  750. Additional Note:  I urge anyone doing ray/triangle intersections to use Didier
  751. Badouel's "An Efficient Ray-Polygon Intersection" (Graphics Gems pp.
  752. 390-393).  I have implemented both Badouel's method and Snyder/Barr's
  753. barycentric method, and Badouel's method is about 19% faster (I optimized the
  754. snot out of my implementation of the barycentric method, but I used most of
  755. those same opts in Badouel's method as well).  This result is from comparing
  756. the same scene ray traced with the two versions.
  757.  
  758. _________________________________________________________________________
  759.  
  760. [A second article followed some days later - EAH]
  761.  
  762. More results from the voxel/shadow optimization:
  763. -----------------------------------------------
  764.  
  765. One thing I neglected to mention in the previous message was that you should
  766. be sure to NULL out your last object and last voxel hit pointers at the end of
  767. each scanline.
  768.  
  769. NEW TEST SCENES:
  770. ---------------
  771. The test scenes producing the results below are 40x40x40 arrays of polygons
  772. (each polygon is broken down into 8 triangles).  The polygons are distributed
  773. at unit distances from each other, and then their orientations are jittered
  774. (rotations) and their positions are jittered (translate of -1.  to +1.).  Each
  775. polygon is roughly a unit in width and height.  The polygons are inside of a
  776. larger box (the room) with 15 shadow casting lights in a 5x3 array just below
  777. the "ceiling".  There were no reflection or refraction rays generated.  All
  778. images were computed at 645x486 pixels with 4 supersamples per pixel.  Every
  779. intersection generated 15 shadow rays.  The "sparse" scene had every polygon
  780. scaled by 0.2 in all dimensions.  The resulting sparse image looks like an
  781. exploding particle system (due mainly to the 145 degree field of view).  In
  782. the dense image, almost no background can be seen.
  783.  
  784. CHART DESCRIPTION:
  785. -----------------
  786. "Last Voxel" speed up refers to the percentage fewer cycles the "last voxel"
  787. method took to compute the same image.  Since this percentage is calculated
  788. based on the number of cycles the entire ray trace took, it is an exact
  789. measure of the speed up.  Negative numbers mean that the "last voxel" method
  790. was slower.  It is important to note that file read, tessellation and spatial
  791. subdivision time is included in the count of the cycles, so the actual speed
  792. up to the ray tracing alone may be greater than is stated, depending on how
  793. you want to measure things.
  794.  
  795. Average Hits Per Ray is included as a general measure of the density of the
  796. scene, it is the number of confirmed ray/triangle intersections divided by the
  797. total number of rays (shadow rays included).  In the sparse scene it is less
  798. than one since most of the shadow rays made it to the light sources without
  799. hitting anything.  The dense scene is greater than one because some confirmed
  800. intersections are abandoned due to nearer intersections being found in the
  801. same voxel.
  802.  
  803. Average Hits Per Primary Ray is the number of confirmed ray/triangle
  804. intersections divided by the number of primary (eye) rays.
  805.  
  806. --------------+-----------------+-----------------+
  807. Scene         | 64,000 jittered | 64,000 jittered |
  808. Description   | polygons (0.2)  | polygons (1.0)  |
  809.           |   (sparse)      |   (dense)       |
  810. --------------+-----------------+-----------------+
  811. Number of     |   551,408       |  551,408        |
  812. Triangles     |                 |                 |
  813. --------------+-----------------+-----------------+
  814. Number of     |                 |                 |
  815. Shadow Casting|       15        |     15          |
  816. Lights        |                 |                 |
  817. --------------+-----------------+-----------------+
  818. Number of Rays|   11,324,318    |  8,427,904      |
  819. --------------+-----------------+-----------------+
  820. "Last Object" |                 |                 |
  821. Success Rate  |       50.7%     |  90.9%          |
  822. --------------+-----------------+-----------------+
  823. "Last Voxel"  |                 |                 |
  824. Success Rate  |       23.4%     |  39.3%          |
  825. --------------+-----------------+-----------------+
  826. "Last Voxel"  |                 |                 |
  827. Speed Up      |       1.04%     |  3.6%           |
  828. --------------+-----------------+-----------------+
  829. Average Hits  |                 |                 |
  830. Per Ray       |       0.265     |  1.001          |
  831. --------------+-----------------+-----------------+
  832. Average Hits  |                 |                 |
  833. Per Primary   |       2.363     |  6.638          |
  834. Ray           |                 |                 |
  835. --------------+-----------------+-----------------+
  836.  
  837. It is encouraging that there is a speedup even in very sparse scenes (however
  838. slight a speed-up it is).  These "random" scenes are not very indicative of
  839. the type of scenes we are generally interested in ray tracing.  (Really, these
  840. scenes look like particle systems, I can think of much better ways to render
  841. them with to produce similar images :^).  So, here's the same chart for the
  842. snare drum with increasing numbers of lights.  The extra lights are scattered
  843. around the "room" and all point towards "Spanky" the snare drum.
  844.  
  845. --------------+---------+---------+---------+
  846. Scene         | Snare 1 | Snare 3 | Snare 6 |
  847. Description   | Shadow  | Shadow  | Shadow  |
  848.           | Light   | Lights  | Lights  |
  849. --------------+---------+---------+---------+
  850. Number of     |  59,692 |  59,692 |  59,692 |
  851. Triangles     |         |         |         |
  852. --------------+---------+---------+---------+
  853. Number of     |         |         |         |
  854. Shadow Casting|    1    |    3    |    6    |
  855. Lights        |         |         |         |
  856. --------------+---------+---------+---------+
  857. Number of Rays| 638,182 |1,097,569|1,737,021|
  858. --------------+---------+---------+---------+
  859. "Last Object" |         |         |         |
  860. Success Rate  |  52.6%  |  89.0%  |  88.7%  |
  861. --------------+---------+---------+---------+
  862. "Last Voxel"  |         |         |         |
  863. Success Rate  |  76.3%  |  77.0%  |  76.9%  |
  864. --------------+---------+---------+---------+
  865. "Last Voxel"  |         |         |         |
  866. Speed Up      |  1.97%  |  3.37%  |  4.39%  |
  867. --------------+---------+---------+---------+
  868. Average Hits  |         |         |         |
  869. Per Ray       |  0.75   |  0.67   |  0.59   |
  870. --------------+---------+---------+---------+
  871. Average Hits  |         |         |         |
  872. Per Primary   |  1.84   |  2.84   |  3.94   |
  873. Ray           |         |         |         |
  874. --------------+---------+---------+---------+
  875.  
  876. Well, the speed-up isn't quite 2% per light as I said in my previous article,
  877. but it is there.  The "last voxel" trick has not slowed down the ray tracing
  878. process in any of these tests which is quite encouraging.
  879.  
  880. ------------------------------------------------
  881.  
  882. Another helpful hint if you are ray tracing tessellated or planar surfaces:
  883. In general when spawning a shadow ray, one must be careful to avoid
  884. intersecting the object just struck.  Usually this is done by adding some
  885. small epsilon to the origin of the shadow ray along it's direction of travel.
  886. However, if you store a ray id with every object (triangle) to record if that
  887. object has been tested against the current ray, then you can use that id to
  888. avoid testing your shadow ray against the intersected object which generated
  889. the shadow ray.  Before spawning the shadow ray, place the id number of the
  890. shadow ray into the ray id field of the object which has just been
  891. intersected.  This method won't work for objects which can self shadow (eg.
  892. parametric or implicit surfaces), but it works fine for planar surfaces (eg.
  893. triangles from surface tessellations).
  894.  
  895. --------------------------------------------------------
  896.  
  897. - Andrew Pearce, Alias Research, Toronto, like Downtown
  898. - pearce%alias@csri.utoronto.ca   |   pearce@alias.UUCP
  899.  
  900. -------------------------------------------------------------------------------
  901.  
  902. Real3d, passed on by Juhana Kouhia (jk87377@tut.fi) and "Zap" Andersson
  903.  
  904. [This was an advertisement on some amiga board.]
  905.  
  906.     Real 3D FEATURES
  907.     ----------------
  908.  
  909. Real 3D is design and animation program for producing high quality, realistic
  910. pictures of three dimensional objects.  It provides an impressive set of
  911. advanced features including:
  912.  
  913. Ray Tracing        A ray tracing of Real 3D is strongly based on the
  914.             physical reality of the real world. Real 3D
  915.             produces pictures by simulating the laws of physics,
  916.             and consequently they represent reality with
  917.             astonishing accuracy.
  918.  
  919. Speed            Innovative methods and new ray tracing algorithms
  920.             make Real 3D really fast. When using fastest ray tracing
  921.             mode, rendering time is typically from 1 to 15 minutes.
  922.  
  923. Hierarchical        With Real 3D you can create hierarchical objects.
  924. Object            This means that objects you create can be made of
  925. Oriented        subobjects, and these subobjects may have their
  926. Construction        own substructure and so on. This kind of a tree
  927. of Objects        structure is well known in the context of disk
  928.             operating systems, in which you can create directories
  929.             inside directories. In Real 3D counterparts of these
  930.             directories are used to collect objects into logical
  931.             groups.
  932.             This kind of approach makes for example object
  933.             modifications extremely easy, because it is possible
  934.             to perform operations to logical entities. If you
  935.             want to copy a DOS directory, you don't have to
  936.             take care of the files and directories inside it.
  937.             In the same manner, you can stretch a complex object in
  938.             Real 3D as easily as one part of it.
  939.  
  940. True Solid        Real 3D includes a true solid modeler. Solid model is the
  941. Model            most sophisticated way to represent three dimensional
  942.             objects. This modeling technique requires much computing
  943.             power and therefore it has earlier been used only in
  944.             environments, which are many times faster than Amiga.
  945.             Now it is possible to Amiga owners to reach all the
  946.             advantages of solid model, thanks to ultimate
  947.             optimizations carried out when developing Real 3D.
  948.  
  949. Smoothly Curved     In addition to plane surfaces, Real 3D includes several
  950. Surfaces        curved surfaces, such as ball, cylinder, cone and
  951.             hyperboloid. This means that no matter how much you
  952.             enlarge a ball created by Real 3D, you don't find
  953.             any edges or corners on its surface. Furthermore,
  954.             this makes the program much faster. And what is most
  955.             important, the produced pictures look really good.
  956.  
  957. Boolean            Solid model allows Boolean operations between objects.
  958. Operations        It is possible, for example, to split an object into
  959.             two pieces and move the pieces apart so that the inner
  960.             structure of the object is revealed.
  961.             Operations can also be done so that the properties of
  962.             the material of the target object are changed. By using
  963.             a brilliant cylinder one can drill a brilliant hole into
  964.             a matt object. Operations are a powerful way to create
  965.             and modify objects. Especially in modeling technical
  966.             objects these Boolean operations are indispensable.
  967.  
  968. Properties of       A user of Real 3D is not restricted to use some basic
  969. Surfaces        surface brilliancies such as matt or shiny. Instead,
  970.             the light reflection properties can be freely adjusted
  971.             from absolute matt to totally mirrorlike, precisely
  972.             to the desired level.
  973.  
  974. Properties of       Due to solid model, it is possible to create objects
  975. Materials        from different materials, which have suitable physical
  976.             properties. Just as surface brilliancy, also transparency
  977.             of a material can be adjusted without any restrictions.
  978.             Even light refraction properties are freely adjustable
  979.             so that it is possible to create optical devices from
  980.             glass lenses. These devices act precisely as their
  981.             real counterparts: a magnifying glass in Real 3D world
  982.             really magnifies!
  983.  
  984. Texture Mapping     The texture mapping properties of Real 3D are not
  985.             restricted to a typical chequered pattern: Any IFF
  986.             picture can be used to paint objects. You can create
  987.             pictures with your favorite painting program as well
  988.             as with a video digitizer or a scanner. For example, by
  989.             digitizing a wood filament pattern, it is easy to create
  990.             wooden objects looking very realistic.
  991.             Pictures can be located precisely to desired places,
  992.             with desired sizes and directions.
  993.             Real 3D offers as many as seven texture mapping methods,
  994.             including parallel, cylinder, ball and spiral projections.
  995.  
  996. Light Sources       Unlimited number of light sources of desired color and
  997.             brightness. The only restriction is amount of memory.
  998.  
  999. Animation        As well as you can create single pictures, you can
  1000. Support            create series of pictures, animations. Real 3D includes
  1001.             also software for representing these animations
  1002.             interactively. Animation representation can be directed
  1003.             by a script language from ascii files or even from
  1004.             keyboard. Instead of looping animations you can define
  1005.             infinitely many ways to represent your pictures. Therefore
  1006.             you can create animations from a small number of pictures
  1007.             by displaying them various ways.
  1008.  
  1009. Rendering        Real 3D includes several different rendering techniques:
  1010. Techniques        a real time wireframe model, a hidden line wireframe model,
  1011.             a high speed one light source ray tracing model,
  1012.             a non-shadow-casting ray tracing model and a perfect ray
  1013.             tracing model. You can select either a HAM display mode
  1014.             with 4096 colors or a grey scale display mode offering
  1015.             higher resolution. Also version with 16 million color
  1016.             rendering (24 bits output) will become available during
  1017.             November 1990.
  1018.  
  1019. Availability        When writing this document (6.9.1990), marketing of
  1020.             Real 3D is already started in Europe with a little
  1021.             lower price than that of Sculpt 4D. The distribution
  1022.             in the USA is not yet arranged. For further information
  1023.             of Real 3D, please contact:
  1024.  
  1025.             REALSOFT KY
  1026.             KP 9, SF-35700 VILPPULA
  1027.             FINLAND
  1028.  
  1029.             Tel. +358-34-48390
  1030.  
  1031. --------
  1032.  
  1033. from "Zap" Andersson:
  1034.  
  1035. REAL3d ('member that?) is available (in Sweden at least) from:
  1036. KARLBERG & KARLBERG AB
  1037. FLADIE KYRKOVAEG
  1038. S-23700 BJARRED
  1039. SWEDEN
  1040. Phone: +46(0)46-47450
  1041. Phax:  +46(0)46-47120
  1042.  
  1043. -------------------------------------------------------------------------------
  1044.  
  1045. Utah Raster Toolkit Patch, by Spencer Thomas
  1046.  
  1047. The first patch for the Utah Raster Toolkit version 3.0 is now available.  The
  1048. patch file is urt-3.0.patch1, and is currently available from cs.utah.edu and
  1049. freebie.engin.umich.edu, and will soon be available from our other archive
  1050. sites (depending on how quickly the archive maintainers grab the patch file).
  1051. There are also slight changes to the files urt-img.tar and urt-doc.tar (in
  1052. particular, if you had trouble printing doc/rle.ps, this is fixed).
  1053.  
  1054. [p.s. there was also a fix to a getx11 bug for the Sun 4, which is
  1055. pub/urt-SUNOS4.1-patch.tar.Z on freebie and weedeater. --EAH]
  1056.  
  1057. Here is the description from the patch file:
  1058.     Fixed core dump in rletogif, compile warnings in giftorle.
  1059.     Minor update bug in getx11 fixed.
  1060.     getx11 now exits if all its input files are bogus.
  1061.     New program: rlestereo, combines two images (left and right eye)
  1062.     into a red-blue (or green) stereo pair.
  1063.     Configuration file for Interactive Systems 386/ix.
  1064.     Minor fix to rleskel: ignore trailing garbage in an input image.
  1065.  
  1066. And the list of the current archive sites, from the urt.README file in
  1067. the ftp directory:
  1068.  
  1069.   North America
  1070.      East coast
  1071.     weedeater.math.yale.edu    130.132.23.17    (pub/*)
  1072.      Midwest
  1073.     freebie.engin.umich.edu    35.2.68.23    (pub/*)
  1074.      West
  1075.     cs.utah.edu        128.110.4.21    (pub/*)
  1076.   Europe
  1077.      Sweden
  1078.     alcazar.cd.chalmers.se    129.16.48.100    (pub/urt/urt-3.0.tar.Z)
  1079.     maeglin.mt.luth.se    130.240.0.25    (pub/Utah-raster/*)
  1080.   Australia
  1081.          ftp.adelaide.edu.au    129.127.40.3    (pub/URT/*)
  1082.     or, if you know what this means:
  1083.         Fetchfile:     sirius.ua.oz in URT
  1084.  
  1085. =Spencer W. Thomas         EECS Dept, U of Michigan, Ann Arbor, MI 48109
  1086. spencer@eecs.umich.edu        313-936-2616 (8-6 E[SD]T M-F)
  1087.  
  1088. -------------------------------------------------------------------------------
  1089.  
  1090. NFF Shell Database, by Thierry Leconte (Thierry.Leconte@irisa.fr)
  1091.  
  1092. [Below is Thierry Leconte's code for an NFF version of the seashell generator
  1093. I listed last issue.  He added some reasonable lights and a view (which I was
  1094. too lazy to do).  I'll probably add it to the 3.0 version of the SPD.  Setting
  1095. "steps" is similar to an SPD SIZE_FACTOR type control.  You'll need the SPD to
  1096. compile and link this program.  -- EAH]
  1097.  
  1098. #include <stdio.h>
  1099. #include <math.h>
  1100. #include "def.h"
  1101. #include "lib.h"
  1102.  
  1103. main(argc,argv)
  1104. int argc;  char *argv[];
  1105. {
  1106. static  double  gamma = 1.0 ;   /* 0.01 to 3 */
  1107. static  double  alpha = 1.1 ;   /* > 1 */
  1108. static  double  beta = -2.0 ;   /* ~ -2 */
  1109. static  int     steps = 600 ;   /* ~number of spheres generated */
  1110. static  double  a = 0.15 ;      /* exponent constant */
  1111. static  double  k = 1.0 ;       /* relative size */
  1112. double  r,x,y,z,rad,angle ;
  1113. int     i ;
  1114. COORD4  back_color, obj_color ;
  1115. COORD4  center, light ;
  1116. COORD4  from, at, up ;
  1117. COORD4  sphere;
  1118.  
  1119. #define OUTPUT_FORMAT    OUTPUT_CURVES
  1120.  
  1121. /* output viewpoint */
  1122. SET_COORD( from, 6, 60, 35 ) ;
  1123. SET_COORD( at, 0.0, 8.0, -15.0 ) ;
  1124. SET_COORD( up, 0.0, 0.0, 1.0 ) ;
  1125. lib_output_viewpoint( &from, &at, &up, 45.0, 0.5, 512, 512 ) ;
  1126.  
  1127. /* output background color - UNC sky blue */
  1128. SET_COORD( back_color, 0.078, 0.361, 0.753 ) ;
  1129. lib_output_background_color( &back_color ) ;
  1130.  
  1131. /* output light sources */
  1132. SET_COORD( light, -100.0, -100.0, 100.0 ) ;
  1133. lib_output_light( &light ) ;
  1134.  
  1135. /* set up sphere color */
  1136. SET_COORD( obj_color, 1.0, 0.8, 0.4 ) ;
  1137. lib_output_color( &obj_color, 0.8, 0.2, 100.0, 0.0, 1.0 ) ;
  1138.  
  1139.     for ( i = -steps*2/3; i <= steps/3 ; ++i ) {
  1140.     angle = 3.0 * 6.0 * M_PI * (double)i / (double)steps ;
  1141.     r = k * exp( a * angle ) ;
  1142.     sphere.x = r * sin( angle ) ;
  1143.     sphere.y = r * cos( angle ) ;
  1144.     /* alternate formula: z = alpha * angle */
  1145.     sphere.z = beta * r ;
  1146.     sphere.w = r / gamma ;
  1147.     lib_output_sphere( &sphere, OUTPUT_FORMAT ) ;
  1148.     }
  1149. }
  1150.  
  1151. -------------------------------------------------------------------------------
  1152.  
  1153. FTP list update and New Software, by Eric Haines, George Kyriazis
  1154.  
  1155. I posted my FTP site list for ray tracing related stuff, and a few people were
  1156. nice enough to write and update this list.  The new list is posted after this
  1157. note from George Kyriazis at RPI (his site has the friendliest login I've ever
  1158. seen):
  1159.  
  1160. --------
  1161.  
  1162. iear.arts.rpi.edu [128.113.6.10]:
  1163.  
  1164. There was an article in IEEE CG&A a while ago from Sandia National Labs (the
  1165. guy's name was Mareda I think) that uses fourier transforms and digital
  1166. filters to create wave height fields from white noise.  What I have in the
  1167. directory is an implementation of this algorithm and a program that raytraces
  1168. it on the AT&T Pixel Machine.
  1169.  
  1170. A list of what exists in there follows:
  1171.  
  1172. graphics-gems:    source code to Glassner's Graphics Gems book.
  1173. ray-tracing-news:What else?
  1174. wave:        Rendering of ocean waves using fft. (Mareda, et. al.)
  1175. coldith:    conversion from my image format to sun rasterfiles
  1176.         and dithering from 32 or 24 bit -> 8 bit rasterfiles.
  1177. drt:        A ray-tracer from the Netherlands by Marinko Laban
  1178. gk:        A distributed raytracer by me.
  1179. microray:    DBW_uRAY by David Wecker
  1180. mtv:        Well, you know what this is.  It probably is an old version.
  1181. non-completed-OO-modeler:
  1182.         Something I was working on.  It barely works, but I put
  1183.         it out there just for the fun of it.
  1184. ohta:        Masataka Ohta's constant time ray-tracer;
  1185.         with a few improvements.
  1186. pxm-and-vmpxm-ray.etc:
  1187.         Two raytracers for the AT&T Pixel Machine.  The second
  1188.         one uses some virtual memory code to store more objects.
  1189.         The VM source is included also.
  1190. qrt:        Well, QRT!
  1191. rayshade:    Rayshade 2.21 by Craig Kolb.
  1192.  
  1193. I hope I'll have a few anonymous ftp sessions after this.. :-)
  1194.  
  1195. --------
  1196.  
  1197. Corrected FTP site list for ray tracing related material:
  1198.  
  1199. weedeater.math.yale.edu [130.132.23.17]:  /pub - *Rayshade 3.0 ray tracer*,
  1200.     *color quantization code*, RT News, *new Utah raster toolkit*, newer
  1201.     FBM, *Graphics Gems code*.  Craig Kolb <kolb@yale.edu>
  1202.  
  1203. cs.uoregon.edu [128.223.4.13]:  /pub - *MTV ray tracer*, *RT News*, *RT
  1204.     bibliography*, other raytracers (including RayShade, QRT, VM_pRAY),
  1205.     SPD/NFF, OFF objects, musgrave papers, some Netlib polyhedra, Roy Hall
  1206.     book source code, Hershey fonts, old FBM.  Mark VandeWettering
  1207.     <markv@acm.princeton.edu>
  1208.  
  1209. hanauma.stanford.edu [36.51.0.16]: /pub/graphics/Comp.graphics - best of
  1210.     comp.graphics (very extensive), ray-tracers - DBW, MTV, QRT, and more.
  1211.     Joe Dellinger <joe@hanauma.stanford.edu>
  1212.  
  1213. freedom.graphics.cornell.edu [128.84.247.85]:  *RT News back issues, source
  1214.     code from Roy Hall's book "Illumination and Color in Computer
  1215.     Generated Imagery", SPD package, Heckbert/Haines ray tracing article
  1216.     bibliography, Muuss timing papers.  [CURRENTLY NOT AVAILABLE]
  1217.  
  1218. alfred.ccs.carleton.ca [134.117.1.1]:  /pub/dkbtrace - *DKB ray tracer*.
  1219.     David Buck <david_buck@carleton.ca>
  1220.  
  1221. uunet.uu.net [192.48.96.2]:  /graphics - RT News back issues (not complete),
  1222.     other graphics related material.
  1223.  
  1224. iear.arts.rpi.edu [128.113.6.10]:  /pub - *Kyriazis stochastic Ray Tracer*.
  1225.     qrt, Ohta's ray tracer, other RT's (including one for the AT&T Pixel
  1226.     Machine), RT News, Graphics Gems, wave ray tracing using digital
  1227.     filter method.  George Kyriazis <kyriazis@turing.cs.rpi.edu>
  1228.  
  1229. life.pawl.rpi.edu [128.113.10.2]: /pub/ray - *Kyriazis stochastic Ray Tracer*.
  1230.     George Kyriazis <kyriazis@turing.cs.rpi.edu>
  1231.  
  1232. xanth.cs.odu.edu [128.82.8.1]:  /amiga/dbw.zoo - DBW Render for the Amiga (zoo
  1233.     format).  Tad Guy <tadguy@cs.odu.edu>
  1234.  
  1235. munnari.oz.au [128.250.1.21]:  */pub/graphics/vort.tar.Z - CSG and algebraic
  1236.     surface ray tracer*, /pub - DBW, pbmplus.  David Hook
  1237.     <dgh@munnari.oz.au>
  1238.  
  1239. cs.utah.edu [128.110.4.21]: /pub - *Utah raster toolkit*.  Spencer Thomas
  1240.     <thomas@cs.utah.edu>
  1241.  
  1242. gatekeeper.dec.com [16.1.0.2]: /pub/DEC/off.tar.Z - *OFF objects*,
  1243.     /pub/misc/graf-bib - *graphics bibliographies (incomplete)*.  Randi
  1244.     Rost <rost@granite.dec.com>
  1245.  
  1246. abcfd20.larc.nasa.gov [128.155.23.64]: /amiga - DBW,
  1247.     /usenet/comp.{sources|binaries}.amiga/volume90/applications -
  1248.     DKBTrace 2.01.  Tad Guy <tadguy@cs.odu.edu>
  1249.  
  1250. expo.lcs.mit.edu [18.30.0.212]:  contrib - *pbm.tar.Z portable bitmap
  1251.     package*, *poskbitmaptars bitmap collection*, *Raveling Img*,
  1252.     xloadimage.  Jef Poskanzer <jef@well.sf.ca.us>
  1253.  
  1254. venera.isi.edu [128.9.0.32]:  */pub/Img.tar.z and img.tar.z - some image
  1255.     manipulation*, /pub/images - RGB separation photos.  Paul Raveling
  1256.     <raveling@venera.isi.edu>
  1257.  
  1258. ftp.ee.lbl.gov [128.3.254.68]: *pbmplus.tar.Z*.
  1259.  
  1260. ucsd.edu [128.54.16.1]: /graphics - utah rle toolkit, pbmplus, fbm, databases,
  1261.     MTV, DBW and other ray tracers, world map, other stuff.  Not updated
  1262.     much recently.
  1263.  
  1264. okeeffe.berkeley.edu [128.32.130.3]:  /pub - TIFF software and pics.  Sam
  1265.     Leffler <sam@okeeffe.berkeley.edu>
  1266.  
  1267. irisa.fr [131.254.2.3]:  */iPSC2/VM_pRAY ray tracer*, /NFF - many non-SPD NFF
  1268.     format scenes.  Didier Badouel <badouel@irisa.irisa.fr>
  1269.  
  1270. surya.waterloo.edu [129.97.129.72]: /graphics - FBM, ray tracers
  1271.  
  1272. vega.hut.fi [128.214.3.82]: /graphics - RTN archive, ray tracers (MTV, QRT,
  1273.     others), NFF, some models
  1274.  
  1275. netlib automatic mail replier:  UUCP - research!netlib, Internet -
  1276.     netlib@ornl.gov.  *SPD package*, *polyhedra databases*.  Send one
  1277.     line message "send index" for more info.
  1278.  
  1279. UUCP archive: avatar - RT News back issues.  For details, write Kory Hamzeh
  1280.     <kory@avatar.avatar.com>
  1281.  
  1282. ======== USENET cullings follow ===============================================
  1283.  
  1284. Humorous Anecdotes, by J. Eric Townsend, Greg Richter, Michael McCool,
  1285.     Eric Haines
  1286.  
  1287.  
  1288. from J. Eric Townsend (jet@uh.edu):
  1289.  
  1290. Went to lunch with a good (but non-technical) friend of mine the other day.
  1291. On the way home, we were talking about what a nice day it was for lying around
  1292. and reading.  She mentioned that she'd gotten a Joyce Carol Oates book I was
  1293. looking for and was going to read it.
  1294.  
  1295. I said, "I wish I had time to read something fun, but I've got to read some
  1296. more ray tracing today for my special problems class."
  1297.  
  1298. She said, "Ray Tracing?  Who's that.  I don't think I've heard of him."
  1299.  
  1300. She thought it was funny only after I stopped laughing and took a few minutes
  1301. to explain it to her.
  1302.  
  1303. Tomorrow, I think I'm going to add a second name to my door (we have slots for
  1304. two as most RA's share offices):  "Ray Tracing".
  1305.  
  1306. --------
  1307.  
  1308. from Greg Richter ({emory,gatech}!bluemtn!greg)
  1309.  
  1310. We had a similar incident with a new secretary who informed me that a salesman
  1311. had called asking about our Gator Rays.  She wanted to know if we were
  1312. involved in animal testing.
  1313.  
  1314. --------
  1315.  
  1316. from Michael McCool (mccool@dgp.toronto.edu)
  1317.  
  1318. >She said, "Ray Tracing?  Who's that.  I don't think I've heard of him."
  1319.  
  1320. For some reason the term seems to collect fun.  At SIGGRAPH in Dallas this
  1321. year the Ray-tracing course organizers [Glassner & Arvo] kept bringing up the
  1322. "related fields" of rat-racing and tray-racing.  Last SIGGRAPH there was a
  1323. "tutorial video" on tray-racing that was shown; it involved sliding trays
  1324. down stairs, and gave examples of acceleration techniques, etc.  One wonders.
  1325.  
  1326. --------
  1327.  
  1328. from Eric Haines:
  1329.  
  1330. And don't forget the t-shirt (a number of Canadians, Calgarians I think, had
  1331. them on):  There's a picture of a nerdy guy holding a pencil and kneeling over
  1332. a man laying on the ground covered with a sheet of paper.  The entire figure
  1333. is labeled "Ray Tracing".  The caption:  "Okee dokee, Ray, here comes Mr.
  1334. Pencil."
  1335.  
  1336. John Wallace also mentioned to me seeing a poster in Denver of jewels with the
  1337. words "Ray Tracy" below, as this was the jeweller's name.
  1338.  
  1339. For those who've moved from graduate work to the world of business, a slogan:
  1340. "Once I was a ray-tracer, now I'm a rat racer."
  1341.  
  1342. I received the "Spherical Aberration" award from Andrew Glassner & Jim Arvo
  1343. for helping organize various ray tracing things.  The award was a glass sphere
  1344. on a wooden base.  It sat on my office windowsill until I moved to a new
  1345. office one day.  Looking at the award, I noticed black marks at the base.  The
  1346. sphere had acted like a (crummy, luckily) magnifying glass and burnt grooves
  1347. in the wood!  It was interesting to see how the marks seemed to correspond to
  1348. the movement of the sun and the seasons.  Anyway, the moral is "Caustics can
  1349. be dangerous" (after all, why do you think they call them "caustic"?).
  1350.  
  1351. -------------------------------------------------------------------------------
  1352.  
  1353. G r a p h i c s   I n t e r f a c e   ' 9 1
  1354.     Calgary, Alberta, Canada
  1355.     3-7 June 1991
  1356.  
  1357. CALL FOR PARTICIPATION
  1358.  
  1359. Graphics Interface '91 is the seventeenth Canadian Conference devoted to
  1360. computer graphics and interactive techniques, and is the oldest regularly
  1361. scheduled computer graphics conference in the world.  Now an annual
  1362. conference, film festival, and tutorials, Graphics Interface has
  1363. established a reputation for a high-quality technical program.  The 1991
  1364. conference will be held in Calgary, Alberta, June 3-7 1991 in conjunction
  1365. with Vision Interface '91. Graphics Interface '91 is sponsored by the
  1366. Canadian Man-Computer Communications Society.
  1367.  
  1368. IMPORTANT DATES:
  1369.  
  1370. Four copies of a Full Paper due:    31 Oct. 1990    *** N O T E ***
  1371. Tutorial Proposals due:            15 Nov. 1990
  1372. Authors Notified:             1 Feb. 1991
  1373. Cover Submissions due:             1 Feb. 1991
  1374. Final Paper due:            29 Mar. 1991
  1375. Electronic Theatre Submissions due:     1 May  1991
  1376.  
  1377. TOPICS:
  1378.  
  1379. Contributions are solicited describing unpublished research results and
  1380. applications experience in graphics, including but not restricted to the
  1381. following areas:
  1382.  
  1383. Image Synthesis & Realism        User Interface
  1384. Shading & Rendering Algorithms        Windowing Systems
  1385. Geometric Modeling            Computer Cartography
  1386. Computer Animation            Image Processing
  1387. Interactive Techniques            Medical Graphics
  1388. Graphics for CAD/CAM            Graphics in Education
  1389. Computer-Aided Building Design        Graphics & the Arts
  1390. Industrial & Robotics Applications    Visualization
  1391. Graphics in Business            Graphics in Simulation
  1392.  
  1393. Four copies of full papers should be submitted to the Program Chairman
  1394. before Oct.31 1990. Include with the paper full names, addresses, phone
  1395. numbers, fax numbers and electronic mail addresses of all the authors. One
  1396. author should be designated "contact author"; all subsequent correspondence
  1397. regarding the paper will be directed to the contact author. The other
  1398. addresses are required for follow-up conference mailings, including the
  1399. preliminary program.
  1400.  
  1401. FOR GENERAL INFORMATION:        SUBMIT PAPERS TO:
  1402.  
  1403. Wayne A. Davis                Brian Wyvill
  1404. GI '91 General Chairman            GI '91 Program Chairman
  1405. Department of Computing Science        Department of Computer Science
  1406. University of Alberta            University of Calgary
  1407. Edmonton, Alberta, Canada        Calgary, Alberta, Canada
  1408. T6G 2H1                    T2N 1N1
  1409.  
  1410. Tel:    403-492-3976            Tel:    403-220-6009
  1411. EMail:    usersams@ualtamts.bitnet    EMail:    blob@cpsc.ucalgary.ca
  1412.  
  1413. [There are often a fair number of papers on ray tracing at this conference
  1414. {vs.  maybe one at SIGGRAPH}, so it is a good place to consider submitting RT
  1415. research.  --EAH]
  1416.  
  1417. -------------------------------------------------------------------------------
  1418.  
  1419. Parametric Surface Reference, by Spencer Thomas
  1420.  
  1421. In article <3632.26f78d3f@cc.curtin.edu.au> Kessells_SR@cc.curtin.edu.au writes:
  1422. > Can someone please tell me where I can find an algorithm for
  1423. > finding the intersection of a ray and a Bezier and/or B-Spline
  1424. > patch.
  1425.  
  1426. You might look at
  1427.  
  1428. Lischinski and Gonczarowski, "Improved techniques for ray tracing
  1429. parametric surfaces," Visual Computer, Vol 6, No 3, June 1990, pp
  1430. 134-152.
  1431.  
  1432. Besides having an interesting technique, they refer to most of the
  1433. other relevant work.
  1434.  
  1435. [This entire issue is dedicated to ray tracing, and is worth checking out.
  1436. -EAH]
  1437.  
  1438. --
  1439. =Spencer W. Thomas         EECS Dept, U of Michigan, Ann Arbor, MI 48109
  1440. spencer@eecs.umich.edu        313-936-2616 (8-6 E[SD]T M-F)
  1441.  
  1442. -------------------------------------------------------------------------------
  1443.  
  1444. Solid Light Sources Reference, by Steve Hollasch, Philip Schneider
  1445. from: comp.graphics
  1446.  
  1447. Steve Hollasch (hollasch@enuxha.eas.asu.edu) writes:
  1448.  
  1449.     How do raytracers make light sources out of arbitrary objects?  I
  1450. thought a while back that one approach would be to find the direction to
  1451. the object from the illuminated point, fire a random cone of rays at the
  1452. object, and assign some fraction of the object's light to the point for
  1453. each unobstructed ray.
  1454.  
  1455.     The main drawback of this approach, as I see it, is that it would
  1456. yield a mottled illuminated area, and the mottling would vary in a
  1457. random manner.
  1458.  
  1459.     About five minutes ago I had an idea for another approach:
  1460.  
  1461.     -  Find the 2D bounding box (from the illuminated point's view) of the
  1462.        illuminating object.
  1463.  
  1464.     -  From this box, get the two orthogonal basis vectors.
  1465.  
  1466.     -  Now subdivide this bounding box (using the basis vectors), just
  1467.        as you would the original raytrace grid.
  1468.  
  1469.     -  For each light ray fired, determine if the ray intersects the
  1470.        illuminating object.  If it does, increment the `silhouette'
  1471.        counter.  If the light ray intersects no other object, then
  1472.        increment the `light' counter.
  1473.  
  1474.     -  Once done, the light that shines on the illuminated point is
  1475.        (light_counter/silhouette_counter) * object_light.
  1476.  
  1477.     This technique would also lend itself to numerous optimizations.
  1478. For example, if you assume that all light objects cast a convex
  1479. silhouette, then you could use binary search techniques to locate the
  1480. edges of the silhouette.  That is, you can assume that all scan lines
  1481. will be runs of space-silhouette-space intersections, hone in on the
  1482. edges, and then multiply the resulting silhouette width by the scanline
  1483. height to get the relative area.
  1484.  
  1485.     Is there a better way to do this?  I haven't come across this
  1486. problem in any of the graphics texts I've read.
  1487.  
  1488. --------
  1489.  
  1490. Philip Schneider (pjs@decwrl.dec.com) replies:
  1491.  
  1492.     Get in touch with the University of Washington Department of Computer
  1493. Science.  Two or three years ago Dan O'Donnell wrote an M.S. thesis
  1494. on what he called "solid light sources".  (Sorry, my copy is in a box
  1495. right now, so I don't recall the exact title :-(
  1496.  
  1497.     Real nice work, as I recall, and the resulting pictures were pretty
  1498. interesting -- one of them featured a coffee mug, with steam rising from it
  1499. that turned into a glowing "neon sign" light formed into the shape of
  1500. the word "Espresso" (of course, I'm biased from having worked alongside him
  1501. at the UW graphics lab :-)
  1502.  
  1503. Philip J. Schneider
  1504. DEC Advanced Technology Development
  1505.  
  1506. [Has anyone seen this thesis?  Could you give me an exact reference (for the
  1507. Ray Tracing Bibliography)?  --EAH]
  1508.  
  1509. -------------------------------------------------------------------------------
  1510.  
  1511. Graphics Gems Source Code Available, by Andrew Glassner, David Hook
  1512.  
  1513. As many readers of the usenet are aware, at Siggraph '90 Academic Press
  1514. released a new book, "Graphics Gems" (edited by Andrew Glassner, published by
  1515. Academic Press, Cambridge MA, 864 pp, $49.95, ISBN 0-12-286165-5).  The book
  1516. is a compilation of many people's work, showing how they solved important
  1517. problems in computer graphics.  Many of the Gems are realized with
  1518. ready-to-run C implementations, presented in two appendices.
  1519.  
  1520. The authors and the publisher are pleased to release this source code to the
  1521. public domain:  neither the authors nor publisher hold any copyright
  1522. restrictions on any of these files.  The code is freely available to the
  1523. entire computer graphics community for study, use, and modification.  We do
  1524. request that the comment at the top of each file, identifying the original
  1525. author and the program's original publication in the book Graphics Gems, be
  1526. retained in all programs that use these files.
  1527.  
  1528. Each Gem is made available on an as-is basis; although considerable effort has
  1529. been expended to check the programs as originally designed and their current
  1530. release in electronic form, the authors and the publisher make no guarantees
  1531. about the correctness of any of these programs or algorithms.
  1532.  
  1533. All source files in the book are now available via anonymous ftp from site
  1534. 'weedeater.math.yale.edu'.  To download the files, connect to this site with
  1535. an ftp program.  For user name type the word 'anonymous'; for password enter
  1536. your last name.  When you are logged in, type 'cd pub/GraphicsGems/src'.  Each
  1537. program from the book is stored in its own plaintext file.  I suggest you
  1538. first download the file README (type 'get README', then quit ftp and open the
  1539. file with any text editor); among other things it describes how to download
  1540. the rest of the directory, identifies the administrator of the site (who will
  1541. collect bug reports, etc.), and provides a table of contents so you can
  1542. identify the source files with their corresponding Gems.
  1543.  
  1544. We have enjoyed putting this book together.  It was a pleasure for me to work
  1545. with the many talented people who contributed to the success of this project.
  1546. A central theme of the book's philosophy was for the results to be practical
  1547. and useful - public release of the source code is a happy result of this
  1548. philosophy, shared by the authors, editor, and publisher.
  1549.  
  1550. We all hope this free source code is a useful resource for programmers
  1551. everywhere.
  1552.  
  1553. --------
  1554.  
  1555. From David Hook:
  1556.  
  1557. AARnet/ACSnet sites can now obtain GraphicGems source code from
  1558. gondwana.ecr.mu.oz.au (128.250.1.63) via anonymous ftp in pub/GraphicsGems or
  1559. through fetchfile, (for a general info file do a "fetchfile
  1560. -dgondwana.ecr.mu.oz pub/GraphicsGems/GEMS.INFO" and for a general listing
  1561. "fetchfile -dgondwana.ecr.mu.oz -LV pub".
  1562.  
  1563. Please note this is a clone site of the GraphicsGems code at
  1564. weedeater.math.yale.edu, and bug reports, etc...  should still be forward to
  1565. the administrators there.  Their addresses are listed in the GEMS.INFO and
  1566. README files.
  1567.  
  1568. --------
  1569.  
  1570. [I felt the following was a good way to summarize much of what "Graphics Gems"
  1571. has in it.  It's excellent, highly recommended (no, I don't have anything in
  1572. it).  Andrew Woo's trick for a quick rejection test on polygons gave me a few
  1573. percent speedup on intersecting these, for example.  Oddly enough, I had tried
  1574. his idea earlier (Kells Elmquist independently discovered it here), but didn't
  1575. get much speedup.  Seeing it in print made me try it again, but this time on a
  1576. variety of databases.  This time it gave some speed-up - the first time I
  1577. tried it on a database particularly ill-suited for performance improvement!
  1578. Finding out that someone else had used it successfully encouraged me to
  1579. explore further.  What's his trick?  You'll have to see the book...  - EAH]
  1580.  
  1581. The table below gives the correspondence between each source
  1582. file in this directory and the name of the Gem it implements.
  1583. Each implementation illustrates one way to realize the
  1584. techniques described by the accompanying Gem in the book.
  1585. The files here contain only the source code for that
  1586. realization.  For a more complete description of the
  1587. algorithms and their applications see the Gems of the same
  1588. name in the first 11 Chapters of the book.
  1589.  
  1590. ---------- header files ----------
  1591. GraphicsGems.h           / Graphics Gems C Header File
  1592.  
  1593. ----------    C code    ----------
  1594. 2DClip               / Two-Dimensional Clipping:
  1595.              A Vector-Based Approach
  1596. AALines                / Rendering Anti-Aliased Lines
  1597. AAPolyScan.c           / Fast Anti-Aliasing Polygon
  1598.              Scan Conversion
  1599. Albers.c               / Albers Equal-Area Conic Map
  1600.              Projection
  1601. BinRec.c               / Recording Animation in Binary Order
  1602.              For Progressive Temporal Refinement
  1603. BoundSphere.c          / An Efficient Bounding Sphere
  1604. BoxSphere.c            / A Simple Method for Box-Sphere
  1605.              Intersection Checking
  1606. CircleRect.c           / Fast Circle-Rectangle Intersection
  1607.              Checking
  1608. ConcaveScan.c          / Concave Polygon Scan Conversion
  1609. DigitalLine.c          / Digital Line Drawing
  1610. Dissolve.c            / A Digital "Dissolve" Effect
  1611. DoubleLine.c           / Symmetric Double Step Line Algorithm
  1612. FastJitter.c           / Efficient Generation of Sampling
  1613.              Jitter Using Look-up Tables
  1614. FitCurves.c            / An Algorithm for Automatically
  1615.              Fitting Digitized Curves
  1616. FixedTrig.c            / Fixed-Point Trigonometry with
  1617.              CORDIC Iterations
  1618. Forms.c                / Forms, Vectors, and Transforms
  1619. GGVecLib.c             / 2D And 3D Vector C Library
  1620. HSLtoRGB.c             / A Fast HSL-to-RGB Transform
  1621. Hash3D.c               / 3D Grid Hashing Function
  1622. HypotApprox.c          / A Fast Approximation to
  1623.              the Hypotenuse
  1624. Interleave.c           / Bit Interleaving for Quad-
  1625.              or Octrees
  1626. Label.c                / Nice Numbers for Graph Labels
  1627. LineEdge.c             / Fast Line-Edge Intersections On
  1628.              A Uniform Grid
  1629. MatrixInvert.c         / Matrix Inversion
  1630. MatrixOrtho.c          / Matrix Orthogonalization
  1631. MatrixPost.c           / Efficient Post-Concatenation of
  1632.              Transformation Matrices
  1633. Median.c               / Median Finding on a 3x3 Grid
  1634. NearestPoint.c         / Solving the
  1635.              Nearest-Point-On-Curve Problem
  1636.              and
  1637.              A Bezier Curve-Based Root-Finder
  1638. OrderDither.c          / Ordered Dithering
  1639. PixelInteger.c         / Proper Treatment of Pixels
  1640.              As Integers
  1641. PntOnLine.c            / A Fast 2D Point-On-Line Test
  1642. PolyScan               / Generic Convex Polygon
  1643.              Scan Conversion and Clipping
  1644. Quaternions.c          / Using Quaternions for Coding
  1645.              3D Transformations
  1646. RGBTo4Bits.c           / Mapping RGB Triples Onto Four Bits
  1647. RayBox.c               / Fast Ray-Box Intersection
  1648. RayPolygon.c           / An Efficient Ray-Polygon
  1649.              Intersection
  1650. Roots3And4.c           / Cubic and Quartic Roots
  1651. SeedFill.c             / A Seed Fill Algorithm
  1652. SquareRoot.c           / A High-Speed, Low-Precision
  1653.              Square Root
  1654. Sturm                  / Using Sturm Sequences to Bracket
  1655.              Real Roots of Polynomial Equations
  1656. TransBox.c             / Transforming Axis-Aligned
  1657.              Bounding Boxes
  1658. TriPoints.c            / Generating Random Points
  1659.              In Triangles
  1660. ViewTrans.c            / 3D Viewing and Rotation Using
  1661.              Orthonormal Bases
  1662.  
  1663. -------------------------------------------------------------------------------
  1664.  
  1665. Graphics Gems Volume 2 CFP, by Sari Kalin
  1666.  
  1667. This is a quick note to let everyone know that Academic Press will be
  1668. publishing a sequel to the book GRAPHICS GEMS, edited by Andrew Glassner.
  1669. Since Andrew decided to take a breather from editing books, I'll be doing the
  1670. honors this time around.  So, if you're interested in contributing a clever
  1671. graphics algorithm or insight (i.e.  a "Gem") to the new volume, contact Sari
  1672. Kalin (the editor at Academic Press) and she'll send you an author's packet.
  1673. Here's the address:
  1674.  
  1675.     Sari Kalin
  1676.     Academic Press
  1677.     955 Massachusetts Ave.
  1678.     Cambridge, MA  02139
  1679.  
  1680.     tel:   (617) 876-3901
  1681.     email: cdp!skalin@labrea.stanford.edu
  1682.  
  1683. AP wants to get the book out by SIGGRAPH `91, so that means the schedule is
  1684. tight.  The submission deadline for first drafts is November 1, 1990, so don't
  1685. delay!  Also, I'm sure AP would appreciate hearing any comments you might have
  1686. about the first volume.
  1687.  
  1688. -------------------------------------------------------------------------------
  1689.  
  1690. Foley, Van Dam, Feiner and Hughes "Computer Graphics" Bug Reports,
  1691.     by Steve Feiner
  1692.  
  1693. Sender: feiner@cs.columbia.edu (Steven Feiner)
  1694. Organization: Columbia University Dept. of CS
  1695.  
  1696. We're in the process of setting up a separate email account to make it easy to
  1697. report bugs, suggest changes, and obtain a copy of the bug list for Computer
  1698. Graphics:  Principles and Practice, 2nd Ed. by Foley, van Dam, Feiner, and
  1699. Hughes.  Since Dave Sklar, the person who is setting up the account, is also
  1700. busting to get the versions of the book's SRGP and SPHIGS graphics packages
  1701. ready for their SIGGRAPH demos, the email account won't be available until
  1702. after SIGGRAPH.  We'll post details as soon as it's up.
  1703.  
  1704. Meanwhile, here are fixes for some dangling references and a missing exercise,
  1705. all of which had been devoured by a hungry gremlin:
  1706.  
  1707. 1) Dangling references:
  1708.  
  1709. FIUM89 Fiume, E.L. The Mathematical Structure of Raster Graphics, Academic
  1710. Press, San Diego, 1989.
  1711.  
  1712. FOUR88 Fournier, A. and D. Fussell,
  1713. ``On the Power of the Frame Buffer,'' ACM TOG, 7(2), April 1988,
  1714. 103-128.
  1715.  
  1716. HUBS82 Hubschman, H. and S.W. Zucker, ``Frame-To-Frame Coherence and the Hidden
  1717. Surface Computation: Constraints for a Convex World,'' ACM TOG, 1(2),
  1718. April 1982, 129-162.  [The bibliography includes HUBS81, the SIGGRAPH 81 paper
  1719. on which HUBS82 was based.]
  1720.  
  1721. SNYD87 Snyder, J.M. and A.H. Barr, ``Ray Tracing Complex Models Containing
  1722. Surface Tessellations,'' SIGGRAPH 87, 119-128.
  1723.  
  1724. TAMM82 Tamminen, M. and R. Sulonen.  ``The EXCELL Method for Efficient
  1725. Geometric Access to Data,'' in Proc. 19th ACM IEEE Design Automation
  1726. Conf., Las Vegas, June 14-16, 1982, 345-351.
  1727.  
  1728. 2) A missing exercise:
  1729.  
  1730. 15.25 If you have implemented the z-buffer algorithm, then add hit detection
  1731. to it by extending the pick-window approach described in Section 7.12.2 to
  1732. take visible-surface determination into account.  You will need a SetPickMode
  1733. procedure that is passed a mode flag, indicating whether objects are to be
  1734. drawn (drawing mode) or instead tested for hits (pick mode).  A SetPickWindow
  1735. procedure will let the user set a rectangular pick window.  The z-buffer must
  1736. already have been filled (by drawing all objects) for pick mode to work.  When
  1737. in pick mode, neither the frame-buffer nor the z-buffer is updated, but the
  1738. z-value of each of the primitive's pixels that falls inside the pick window is
  1739. compared with the corresponding value in the z-buffer.  If the new value would
  1740. have caused the primitive to be drawn in drawing mode, then a flag is set.
  1741. The flag can be inquired by calling InquirePick, which then resets the flag.
  1742. If InquirePick is called after each primitive's routine is called in pick
  1743. mode, picking can be done on a per-primitive basis.  Show how you can use
  1744. InquirePick to determine which object is actually visible at a pixel.
  1745.  
  1746. Steve Feiner
  1747. feiner@cs.columbia.edu
  1748.  
  1749. -------------------------------------------------------------------------------
  1750.  
  1751. Radiosity via Ray Tracing, by Pete Shirley (shirley@iuvax.cs.indiana.edu)
  1752. from: comp.graphics
  1753.  
  1754.  
  1755. kaufman@delta.eecs.nwu.edu (Michael L. Kaufman) writes:
  1756.  
  1757. >This may be a stupid question, but why can't radiosity be handled by ray
  1758. >tracers?  Also, are there any archives that contain code/papers on radiosity
  1759. >that I can learn from?
  1760. >Michael
  1761.  
  1762. Ray Tracers can indeed do radiosity.  Check out the Sillion and Puech paper
  1763. or the Wallace et al. paper in Siggraph '89.  Also the Airey et al. paper
  1764. in proceedings of the symposium of Interactive 3D graphics (Computer
  1765. Graphics 24 (2)), and my Graphics Interface 90 paper.  Also Heckbert's
  1766. Siggraph 90 paper.
  1767.  
  1768. If all you want is a brute force radiosity code (and this code works pretty
  1769. well), then start with N polygons.  Each polygon will have reflectivity Ri
  1770. and will emit power Ei.   Assume you want to send R rays on the first pass.
  1771. We will now do what amounts to physical simulation:
  1772.  
  1773. T = 0           // T is total emitted power
  1774. For i = 1 to N
  1775.     Ui = Ei    // Ui is unsent power
  1776.     Pi = Ei    // Pi is total power estimate
  1777.     T = T + Ei
  1778.  
  1779. dP = T / R       // dP is the approximate power carried by each ray
  1780. For b = 1 to NumReflections
  1781.    For i = 1 to N
  1782.     r = int(Ui / dP)  // patch i will send power Ui in r rays
  1783.     dPi = Ui / r
  1784.     Ui = 0
  1785.     for j = 1 to r
  1786.         choose random direction with cosine weighting and
  1787.          send ray with until it hits polygon p (see Ward et al.
  1788.         Siggraph 88 paper equation 2 p 87)
  1789.  
  1790.         Up = Up + Rp * dPi
  1791.         Pp = Pp + Rp * dPi
  1792.  
  1793.  
  1794. // Once this is done, we will have the power Pi coming from each surface,
  1795. // Now we should convert to radiance (see my GI 90 paper or Kajiya's
  1796. // Course notes in Siggraph 90 Advanced RT notes)
  1797.  
  1798. For i = 1 to N
  1799.     Li = Pi / (pi * Ai)  // Li is radiance, pi is 3.14..., Ai is area
  1800.  
  1801.  
  1802. This ignores interpolation to polygon vertices to give a smooth image
  1803. (see Cohen & Greenberg siggraph 85 figure 8A).
  1804.  
  1805.  
  1806. You might also want to check out Ward et al.'s Siggraph 88 paper.  Not true
  1807. radiosity, but is ray tracing based and has some of the best features
  1808. of ray tracing methods.  If your scene is all diffuse, that method may be
  1809. the way to go.
  1810.  
  1811. -------------------------------------------------------------------------------
  1812.  
  1813. Algorithm Order Discussion, by Masataka Ohta, Pete Shirley
  1814.  
  1815.  
  1816. In article <1150@mti.mti.com> adrian@mti.UUCP (Adrian McCarthy) writes:
  1817.  
  1818. >Rather than using recursive or hierarchical
  1819. >spatial subdivision techniques to reduce ray-object intersection tests
  1820. >(which are of O(log n) algorithms)
  1821.  
  1822. Can you prove it? I think (but can't prove) hierarchical spatial
  1823. subdivision is only O(n**(1/3)).
  1824.  
  1825. >many instances can use a surface map for
  1826. >a single bounding volume as a lookup table to immediately determine a small
  1827. >subset of objects to test (which is truly of O(1)). (Small subset here is
  1828. >roughly equivalent to the set of objects in the smallest volume in a
  1829. >comparable hierarchical scheme.)
  1830.  
  1831. I already published an O(1) ray tracing algorithm (See "An introduction
  1832. to RAY TRACING" edited by Andrew S. Glassner, Academic Press, 6.3 The Ray
  1833. Coherence Algorithm, page 232-234, or, "Computer Graphics 1987 (Proc.
  1834. of CG International '87)", page 303-314, Ray Coherence Theorem and
  1835. constant time ray tracing algorithm).
  1836.  
  1837. Judging from the above brief description of your algorithm, it may be
  1838. similar or identical to mine.
  1839.  
  1840. >It's *not* general,
  1841.  
  1842. Hmmm, mine is general.
  1843.  
  1844. --------
  1845.  
  1846. Kaplan also has claimed a constant time algorithm.  I don't believe that
  1847. his is constant time - it (like an octree) is a divide and conquer
  1848. search, so it will AT BEST be O(logN)  (it takes O(logN) time to travel
  1849. down the height of a tree).
  1850.  
  1851. I don't really see how we can even say what the big-O of a ray intersection
  1852. is without precisely stating what rays are allowed on what geometry.
  1853. For example, suppose I set up N epsilon radius spheres in random locations
  1854. within a cube, where epsilon is small.  In the typical case a ray might
  1855. come close to many spheres.  If an octree is used, the candidate sets
  1856. of many leaves might be checked (worse than O(logN)).  If all of the spheres
  1857. have the same center, how can any scheme get a candidate set for a ray
  1858. through the center that doesn't include all spheres?  This would be
  1859. O(NlogN) for an octree and O(N) optimally.  How would your method be O(1)?
  1860. It seems that often we have good algorithm behavior in practice with
  1861. pathological cases giving terrible big-Os.  Perhaps we can bound the set
  1862. of scenes somehow?
  1863.  
  1864. --------
  1865.  
  1866. Ohta replies:
  1867.  
  1868. >Kaplan also has claimed a constant time algorithm.  I don't believe that
  1869. >his is constant time--
  1870.  
  1871. I agree with you. I know what is O(1).
  1872.  
  1873. >I don't really see how we can even say what the big-O of a ray intersection
  1874. >is without precisely stating what rays are allowed on what geometry.
  1875.  
  1876. Well, it is assumed that, ray object intersection calculation takes only
  1877. constant time. That is, to ray trace a surface defined by N-th degree
  1878. polynominal in constant time regardless to N, is just impossible.
  1879.  
  1880. >For example, suppose I set up N epsilon radius spheres in random locations
  1881. >within a cube, where epsilon is small.  In the typical case a ray might
  1882. >come close to many spheres.  If an octree is used, the candidate sets
  1883. >of many leaves might be checked (worse than O(logN)).  If all of the spheres
  1884. >have the same center, how can any scheme get a candidate set for a ray
  1885. >through ythe center that doesn't include all spheres?  This would be
  1886. >O(NlogN) for an octree and O(N) optimally.  How would your method be O(1)?
  1887.  
  1888. Good question.  But, first, we should make it clear what is constant time ray
  1889. tracing.  As for the per-scene complexity, no algorithm (including your first
  1890. example) can be better than O(N) just because of input complexity (reading all
  1891. the input takes O(N) time).  So, we should talk about complexity to trace a
  1892. single ray.
  1893.  
  1894. My algorithm may consume possibly long and computationally complex
  1895. pre-processing time to analyze a scene.  But, the important fact is that the
  1896. time for pre-processing is dependent only on the scene and not on the number
  1897. of rays.
  1898.  
  1899. And, after pre-precessing, all rays can be traced in constant time.
  1900.  
  1901. With your example of co-centric spheres (assuming epsilon radius is different
  1902. on each sphere, or the problem is reduced to too trivial to trace a single
  1903. sphere), each sphere should further be subdivided into smaller pieces to
  1904. obtain constant time property.  With such a finer subdivision, even octree
  1905. method may be able to do better than O(NlogN).
  1906.  
  1907. >It seems that often we have good algorithm behavior in practice with
  1908. >pathological cases giving terrible big-Os.  Perhaps we can bound the set
  1909. >of scenes somehow?
  1910.  
  1911. It may be reasonable to define complexity of a scene by the complexity of
  1912. pre-processing to obtain constant-timeness.
  1913.  
  1914. --------
  1915.  
  1916. In a separate note, Ohta writes:
  1917.  
  1918. >Can you prove it? I think (but can't prove) hierarchical spatial
  1919. >subdivision is only O(n**(1/3)).
  1920.  
  1921. I have found it is obvious.  All spatial subdivision is at most O(n**(1/3)) if
  1922.  
  1923.     1) Objects are tiny
  1924.     2) Objects are uniformly scattered in space
  1925.  
  1926. 1) means that the possibility of intersection is negligible.
  1927. 2) means at least O(n**(1/3)) subspace must be traversed.
  1928.  
  1929. -------------------------------------------------------------------------------
  1930.  
  1931. Point in Polygon, One More Time..., by Mark Vandewettering, Eric Haines,
  1932.     Edward John Kalenda, Richard Parent, Sam Uselton, "Zap" Andersson, and
  1933.     Bruce Holloway
  1934.  
  1935.  
  1936. Mark VandeWettering writes about the point in polygon test:
  1937.  
  1938. The solution proposed by rusmin@twinsun.com was based upon the Jordan Curve
  1939. theorem: any ray from inside a polygon crosses an odd number of edges on its
  1940. way to infinity.  He chose a random ray that began at the point in question,
  1941. and counted the number of intersections.  Problem: if you intersected a vertex
  1942. you were kind of clueless.  Solution, fire another ray.
  1943.  
  1944. You solve these problems by simplifying everything.  The ray you shoot should
  1945. go to the positive X axis.  Assume without loss of generality that your
  1946. point is the origin.  Now: if you are going to intersect a vertex, its because
  1947. the y component of an edge endpoint is == 0.  Well, decide whether you want
  1948. to count this as positive or negative.  Assume positive (I always do).  It
  1949. turns out you get the right answer anyway.  For example
  1950.  
  1951.       origin         ^
  1952.              |
  1953.     o         o            counts as one intersection
  1954.              |
  1955.              v
  1956.  
  1957.       origin         ^ ^
  1958.              |/
  1959.     o         o            counts as zero or two intersections
  1960.  
  1961.       origin
  1962.  
  1963.     o         o            counts as zero or two intersections
  1964.              |\
  1965.              v v
  1966.  
  1967.  
  1968. Voila!  C'est explique!
  1969.  
  1970.  
  1971. [and in a later note:]
  1972.  
  1973. Hardly my own idea.  It was shown to me by Eric Haines originally, but I don't
  1974. think he claims credit for it either.  Any takers?  Is it patented by Unisys
  1975. as well :-)?
  1976.  
  1977. --------
  1978.  
  1979. Eric Haines [the crazy fool!] replies:
  1980.  
  1981.     Anyway, having an ego and all that, I do indeed claim to be the
  1982. inventor of the "consider all points on the line to be above the line"
  1983. solution, which gets rid of those pesky special cases where vertices are on the
  1984. test ray.  I started with some very complicated special case code in 1986
  1985. which worried about whether the points were on the ray.  Months went by...
  1986. One day, looking at the code, I noticed another stupid special case that I
  1987. didn't handle correctly (something like "if the last point is on the ray and
  1988. the first point is on the ray...").  I looked at the problem again and
  1989. realized that the only property of the ray that I really cared about was that
  1990. it was a divider, not that it was a set of points forming a ray.  Eureka,
  1991. Arkansas!  Get rid of those points, and so define away the problem - no points
  1992. can lie on the ray, if we define the ray as having no points.  O happy day, it
  1993. even worked.  Anyway, it's all written up in my section of "An Introduction to
  1994. Ray Tracing", edited by Andrew Glassner, Academic Press.
  1995.  
  1996.     Historical note:  the earliest reference I have to the point in
  1997. polygon test is the classic "A Characterization of Ten Hidden-Surface
  1998. Algorithms" by Ivan Sutherland et al, 1974, ACM Computing Surveys v6 n1.  This
  1999. has both the ray crossing test and the sum of the angles test, plus the convex
  2000. polygon test (check if the point is inside all lines by substitution into each
  2001. edge's 2D line equation).
  2002.  
  2003.     Computational geometry fiends noted that the method has the problem of
  2004. being indeterminate on edges:  if your intersection point is exactly on an
  2005. edge, it's arbitrary whether the point is determined to be inside or outside
  2006. the polygon (that is, do you consider an edge crossing the point to be to the
  2007. right or left of the point, or do you want a third category, such as "on"?).
  2008.  
  2009.     However, there is a general consistency to the ray crossing test for
  2010. ray tracing.  If the point being tested is along the edge joining two visible
  2011. polygons (which both face the same general direction, i.e. not a silhouette
  2012. edge) and the polygons are projected consistently upon the plane perpendicular
  2013. to the ray, the point is guaranteed to be considered to be inside one and only
  2014. one of the polygons.  That is, no point will be considered within any two
  2015. non-overlapping polygons, nor will it "fall in the crack" between polygons.
  2016.  
  2017.     Think about it this way:  if points on the left edges of the polygon
  2018. are considered outside, then the points on the right edges will be considered
  2019. inside.  This is because we would then consider an edge crossing the x axis at
  2020. exactly 0 as being to the right of the test point.  Since one polygon's left
  2021. edge is another's right edge, it all balances out to make each point be inside
  2022. only one polygon in a polygon mesh.  Horizontal edges are treated the same
  2023. way:  if a point is actually on such an edge, when tested, the point will be
  2024. categorized as "below" the edge consistently.  This will lead it to be inside
  2025. one and only one polygon in a mesh.
  2026.  
  2027.     In reality, when ray tracing you very rarely get points that are
  2028. exactly on an edge, so this is something of a non-problem.  But if you really
  2029. really care about this possibility, make sure to always cast your polygons
  2030. onto the plane perpendicular to the ray (this plane is also good for
  2031. consistency if you want to get edges for Gouraud RGB interpolation, Phong
  2032. normal interpolation, etc).
  2033.  
  2034.     Finally, for you incredibly demonic CompGeom types: yes, indeed,
  2035. points on silhouette edges are still inconsistent.
  2036.  
  2037. P.S.  As our patent on the 90 degree angle was successful, the pending patent
  2038. on the Jordan Curve Theorem should come through any day now... ;-)
  2039.  
  2040. --------
  2041.  
  2042. Edward John Kalenda replies:
  2043.  
  2044. Sorry to be a poop Eric, but my boss at Calma, Steve Hoffman, told me
  2045. about the "points on the ray are above the ray" thing in 1981. He claimed
  2046. someone told HIM several years before.
  2047.  
  2048. I think it's one of those things that just need to be attributed to the
  2049. anonymous coder.
  2050.  
  2051. --------
  2052.  
  2053. I reply:
  2054.  
  2055.     Oh, well, at least I can claim to be the first to publish!  Sadly
  2056. enough, the word still hasn't fully percolated out.  The latest Foley & Van
  2057. Dam (& Feiner & Hughes) says on page 34:  "Next, choose a ray that starts at
  2058. the test point and extends infinitely in any direction, and that does not pass
  2059. through any vertices".  Page 339 makes reference to "intersections at vertices"
  2060. being a "special case".  Passing through a vertex is still considered to be a
  2061. problem (even though it isn't).
  2062.  
  2063.     It's this kind of thing that makes me happy to see books like
  2064. "Graphics Gems" come out.  Letting the world know about the little tricks of
  2065. the trade saves us all a lot of time and replication of effort (I sure wish I
  2066. had known about the "above the ray" trick in 1986 - it would have saved me
  2067. hours of struggle).
  2068.  
  2069. --------
  2070.  
  2071. Richard Parent (parent@cis.ohio-state.edu) writes:
  2072.  
  2073. With respect to 'consider all the points on the line to be above the line',
  2074. both Steve Levine (Ph.D. from Stanford, I believe) and myself discussed
  2075. this as a solution we used in our respective problems; mine was implementing
  2076. Lourtrel's hidden line routine and I imagine his had to do with the
  2077. hierarchical clipping he was doing.  This was at one of the Siggraph's in the
  2078. mid to late seventies, '76, if I had to guess.  It's been around for awhile.
  2079.  
  2080. --------
  2081.  
  2082. I reply:
  2083.  
  2084.     I guess I could compare myself to Leibniz vs. Newton (both
  2085. independently discovering calculus), but I'm probably more in the class of the
  2086. guy that discovers that Wintergreen Life Savers give off sparks when chewed in
  2087. the dark.
  2088.  
  2089. --------
  2090.  
  2091. Sam Uselton writes:
  2092.  
  2093. I've been off news for a few days and just saw your posting of sept 6.  Isn't
  2094. the "consider all points on the line to be above the line" the same as
  2095. "shortening an edge to prevent the vertex lying on the scan line" as suggested
  2096. in Foley & Van Dam (the old one) when describing polygon scan conversion?
  2097. That's not the first place I heard this idea either, it was just the easiest
  2098. reference to grab off the shelf.
  2099.  
  2100. I think this is one of those solutions that is just subtle enough that most
  2101. people don't think of it themselves and think it is neat when they see it but
  2102. just obvious enough that a few people every year re-invent it, and go showing
  2103. it around to others.  Just the kind of thing IMHO that makes Glassner's
  2104. collection and the RTNews such useful things, because it probably couldn't get
  2105. published "traditionally" .
  2106.  
  2107. Trying VERY hard to pull up archival storage, I'm pretty sure I saw this first
  2108. while still at UTD in grad school, which means Henry Fuchs was probably
  2109. explaining it.  Whether he is one of the many originators or he got it from a
  2110. fellow Utah grad student, I couldn't guess.  (Oh, yeah.  Time?  1975-1979).
  2111.  
  2112. --------
  2113.  
  2114. I note:
  2115.  
  2116. For scan conversion it is still a bit tricky:  you have to think a bit about
  2117. where edges begin and end (you want edges with vertices exactly on the scan
  2118. line to be handled correctly, e.g. if the edge's maximum y ends on the scan
  2119. line, delete this edge just before checking scan line).  This kind of problem
  2120. goes away for ray tracing, since you don't have to worry about active edges,
  2121. etc.
  2122.  
  2123. --------
  2124.  
  2125. Sam replies:
  2126.  
  2127. After a weekend of R&R old memory is more easily accessible.  I seem to
  2128. associate my first connection with point in polygon/ ray intersection/ Jordan
  2129. curve theorem/etc etc to an informal seminar, led by Henry Fuchs and Zvi
  2130. Kedem, attended by Alain Fournier, Don Fussell, Jose Barros, myself, and I
  2131. think Bruce Naylor, in which we read and studied early Michael Shamos papers
  2132. (Shamos & Hoey, Bentley & Shamos...).  Must have been about 1978 or so.
  2133.  
  2134. --------
  2135.  
  2136. I reply:
  2137.  
  2138.     Thanks for the info.  What I find amazing about all this is that
  2139. somewhere, somewhere this was not mentioned in the ray tracing literature
  2140. before "An Intro to RT".  Until you (and others) pointed out that this problem
  2141. and solution is analogous to the scan-line problem, I honestly hadn't made the
  2142. connection!  Nor, it seems, had anyone else in print.  Sedgewick's
  2143. "Algorithms" talks about this problem but doesn't give a "points above the
  2144. ray" solution, Berlin in 1985 SIGGRAPH course notes gives a few solutions to
  2145. the problem, but says that test rays through vertices are a special case & are
  2146. very nasty.  Certainly Cornell's ray tracer didn't solve this problem.
  2147. Glassner used the sum of the angles method, so he didn't know about it, so UNC
  2148. didn't know about it.  Sounds like somewhere out west was the point of origin,
  2149. but it never made it east of the Mississippi.  Curious.
  2150.  
  2151.     Sutherland et al's 1974 paper "A Characterization of Ten Hidden
  2152. Surface Algorithms" mentions the problem as a problem ("care is required to
  2153. get consistent results").  Anyway, sounds like there probably wasn't a
  2154. solution before them (if anyone would know, I would think it would be them).
  2155. Interesting puzzle to try to figure out the identity of this anonymous
  2156. programmer.
  2157.  
  2158. --------
  2159.  
  2160. From "Zap" Andersson:
  2161.  
  2162. As I think I posted earlier, this is somewhat similar to my own approach in
  2163. getting rid of special cases: Assume we are testing for a ray along X axis...
  2164. For all line segments, swap 'em, so it's "first" point is upwards (Have a lower
  2165. Y coordinate). Then, for each segment, test if the point's Y > firstY. If not,
  2166. discard (This, in essence, is a version of Eric's idea, only mine :-) then,
  2167. check if Y <= lastY. If not, discard. IMPORTANT ISSUE HERE is that I actually
  2168. CARE about the 'second' point of the line, and include it in the check, that's
  2169. MY way of getting rid of problem of a corner pointing downwards: It will yield
  2170. 2 intersections, Eric's method yields none. No big deal, really.... after
  2171. this simple boundstest, it's time for the dreary math on checking if the
  2172. intersection is on POSITIVE X, i.e. if X > firstX && X > lastX, discard, and
  2173. last but not least, check the real intersection with some math (Left as an
  2174. exercise for the reader :-).
  2175.  
  2176. OBTW, fr'got! FIRST, you check if (LastY - Y) * (FirstY - Y) is > 0. If so,
  2177. discard.
  2178.  
  2179. --------
  2180.  
  2181. Bruce Holloway posts:
  2182.  
  2183. In article <1990Sep11.163420.13592@odin.corp.sgi.com> robert@sgi.com writes:
  2184. >
  2185. >In article <KPS5FNC@xds1.ferranti.com>, peter@ficc.ferranti.com (Peter
  2186. >da Silva) writes:
  2187. >|> In article <33619@cup.portal.com> ekalenda@cup.portal.com (Edward
  2188. >John Kalenda) writes:
  2189. >|> > Sorry to be a poop Eric, but my boss at Calma, Steve Hoffman, told me
  2190. >|> > about the "points on the ray are above the ray" thing in 1981. He claimed
  2191. >|> > someone told HIM several years before.
  2192. >|> >
  2193. >|> > I think it's one of those things that just need to be attributed to the
  2194. >|> > anonymous coder.
  2195. >|>
  2196. >|> Another of those obvious techniques like the XOR-cursor. Good thing nobody
  2197. >|> patented *this* one...
  2198. >
  2199. >I didn't see any smiley's after this one Peter.  I'm sure that
  2200. >many readers don't realize that the XOR-cursor in hardware *IS* patented.
  2201. >
  2202. >... and that's not the only obvious technique that this particular
  2203. >company has a patent on.
  2204.  
  2205. This thread is a riot.  My old boss at Calma, Joe Sukonick, patented the
  2206. XOR-cursor technique based on work he did around 1974, when I went to work
  2207. there.  I remember meeting Jim Clark for the first time around 1979 in front
  2208. of Stacey's bookstore in Palo Alto before he became famous for the Geometry
  2209. Engine.  He was married to a friend of mine from Calma (whom we were all in
  2210. love with!) & said he didn't think Joe's patent was valid because it wasn't
  2211. original.  I agree with him.
  2212.  
  2213. One of the things the patent says is that XOR works because it is "idempotent".
  2214. Joe had a Ph.D. in math from MIT & liked to use words like that, but I thought
  2215. AND & OR were idempotent & XOR worked because it wasn't!  What you need is
  2216. any operation that can be undone, or inverted, like ADD, say.  (What is XOR
  2217. but an ADD without carry?)  Anyway, the patent is now owned by Cadtrak, a
  2218. corporate shell whose charter is to sue everyone under the sun over that
  2219. patent.  Last I heard, Western Digital was going to take them to court to
  2220. overturn it.
  2221.  
  2222. Now as to the "points on the ray are above the ray", this is really the same
  2223. as the idea of half-open intervals which has broad usage in computer graphics.
  2224. When you point-sample a polygon, this is how you make sure that rectangles
  2225. of area m*n hit exactly m*n pixels, even if they lie on your sample grid.
  2226. When I was just a kid at Calma, I wrote two programs that used that idea.
  2227. One was a program to cross-hatch concave (and convex) polygons for making
  2228. plots of overlapping layers on ICs.  Another was a program which intersected
  2229. arbitrary closed polygons with each other.  This was an application program
  2230. written in Calma's GPL which was used to calculate the capacitance between
  2231. layers of a chip, by finding the areas of all the overlaps.  Both of these
  2232. algorithms needed to use the half-open idea to take care of the corner cases.
  2233.  
  2234. I left Calma in 1976, too inexperienced to realize what a singular place it
  2235. had been.  After the ownership changed, most everyone scattered to the four
  2236. corners of the globe.  Later, I actually had a contract job working for
  2237. Cal & Irma Hefte, the founders of Calma.  Cal passed away some years ago--
  2238. he seemed to me to be a lot like Willy Loman in "Death of a Salesman".
  2239. He told me "people are the most complicated & interesting things in the
  2240. world".  Mrs. Hefte and her daughters have a flower shop on Blossom Hill Rd.
  2241. A genuine Silicon Valley story!  (There's a lot more.)
  2242.  
  2243. -------------------------------------------------------------------------------
  2244.  
  2245. Quadrant Counting Polygon In/Out Testing, by Craig Kolb, Ken McElvain
  2246. from: comp.graphics
  2247.  
  2248. [After all that, I thought it was worth posting some real live code, but
  2249. instead for a quadrant counting method that is almost the same as the point in
  2250. polygon ray test.  The "infinite ray" test is really counting quadrants (in
  2251. "An Intro to RT" I show how you can get the winding number using it), but does
  2252. not bother to evaluate the exact quadrant unless need be.  For example, if
  2253. both endpoints of an edge are in the +Y space, we have no need to evaluate
  2254. whether we're in +X or -X.  -EAH]
  2255.  
  2256. In article <1990Mar29.171010.28348@agate.berkeley.edu> raymond@sunkist.UUCP
  2257. (Raymond Chen) writes:
  2258.  
  2259. >Nobody yet has mentioned my favorite method for point-in-polygon
  2260. >detection:  Using the winding number.
  2261.  
  2262. [...]
  2263.  
  2264. >/* Point in polygon detection.  Original author unknown.
  2265. > * Except where noted, I have NOT edited the code in any way.
  2266. > * I didn't even fix the misspellings.  (And no, I don't code
  2267. > * in this style.)
  2268. > */
  2269.  
  2270. [...]
  2271.  
  2272. >    return(quad);    /**rjc**/ /* for some reason, the original
  2273. >                     author left out this crucial line! */
  2274. >}
  2275. >--
  2276. >A remark:  The whichquad function is not perfect.  It doesn't handle
  2277. >the boundary cases right (but as I said, that's only a problem
  2278. >if the point lies on the polygon).
  2279.  
  2280. (After a long-overdue search through my archives...)
  2281.  
  2282. The code was posted to comp.graphics in February of '88 by Ken McElvain
  2283. (decwrl!sci!kenm).  Regarding the typos and the boundary cases, Ken wrote:
  2284.  
  2285. > I pulled this out of some other code and hopefully didn't break it in
  2286. > doing so.  There is some ambiguity in this version as to whether a point
  2287. > lying on the polygon is inside or out.  This can be fairly easily
  2288. > detected though, so you can do what you want in that case.
  2289.  
  2290. I once did a number of tests on Ken's winding number code and an implementation
  2291. of the 'ray' algorithm, using a ray tracer (rayshade).  For the test scenes
  2292. I rendered, I found that the winding number method was approximately 10% faster
  2293. than the ray method.  Your mileage may vary.
  2294.  
  2295. [It surprises me that this algorithm is ever faster:  the infinite ray
  2296. solution is essentially the same idea as the quadrant idea, except that it
  2297. avoids x compares when the signs of the y components are the same.  Maybe I'll
  2298. hack rayshade & prove it someday...  -- EAH]
  2299.  
  2300. From: kenm@sci.UUCP (Ken McElvain)
  2301. Organization: Silicon Compilers Systems Corp. San Jose, Ca
  2302.  
  2303. In article <5305@spool.cs.wisc.edu>, planting@speedy.cs.wisc.edu (W. Harry Plantinga) writes:
  2304. > In article <7626@pur-ee.UUCP> beatyr@pur-ee.UUCP (Robert Beaty) writes:
  2305. > >In article <20533@amdcad.AMD.COM> msprick@amdcad.UUCP (Rick Dorris) writes:
  2306. > >>In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC) writes:
  2307. > >>>Have a nice one here:
  2308. > >>>Have a boundary defined on the screen. Boundary is composed of points
  2309. > >>>joined by lines... Now some random points are generated and I want to check
  2310. > >>>if a given point is within or outside the existing boundary.. Any algorithm for
  2311. > >> <rick suggests the infinite ray/intersection counting algorithm>
  2312. > >
  2313. > >I have seen this type of algorithm before and the one I thought up
  2314. > >in an afternoon is FAR superior and vastly simpler to code up.
  2315. > >
  2316. > ><robert beaty suggests an algorithm that measures sums the angles of
  2317. > >the lines connecting the points and the test point>
  2318. >
  2319. > Haven't I seen this discussion of point-in-polygon algorithms about 15
  2320. > times before? :-)
  2321. >
  2322. > Robert, your algorithm is simpler only in the kind of problems it
  2323. > handles.  It will only work for convex polygons, whereas the other
  2324. > works for any polygons.  It's not even much simpler; measuring angles
  2325. > and determining whether line segments intersect are of comparable
  2326. > difficulty.
  2327. >
  2328. > Maybe you should have said that although your algorithm is far
  2329. > inferior, it's not any easier to code?
  2330.  
  2331.  
  2332. Robert's suggestion is a good one.  The sum of the angles about the
  2333. test point is known as the winding number.  For non intersecting
  2334. polygons if the winding number is non-zero then the test point is
  2335. inside the polygon.  It works just fine for convex and concave
  2336. polygon's.  Intersecting polygon's give reasonable results too.
  2337. A figure 8  will give a negative winding number for a test point
  2338. in one of the loops and a positive winding number for the other loop,
  2339. with all points outside having a winding number of 0.  Other advantages
  2340. of the winding number calculation are that it does not suffer from
  2341. the confusion of the infinite ray algorithm when the ray crosses a vertex
  2342. or is colinear with an edge.
  2343.  
  2344. Here is my version of a point in poly routine using a quadrant
  2345. granularity winding number.  The basic idea is to total the angle
  2346. changes for a wiper arm with its origin at the point and whos end
  2347. follows the polygon points.  If the angle change is 0 then you are
  2348. outside, otherwise you are in some sense inside.  It is not necessary to
  2349. compute exact angles, resolution to a quadrant is sufficient, greatly
  2350. simplifying the calculations.
  2351.  
  2352. I pulled this out of some other code and hopefully didn't break it in
  2353. doing so.  There is some ambiguity in this version as to whether a point
  2354. lying on the polygon is inside or out.  This can be fairly easily
  2355. detected though, so you can do what you want in that case.
  2356.  
  2357.  
  2358. --------
  2359. /*
  2360.  * Quadrants:
  2361.  *    1 | 0
  2362.  *    -----
  2363.  *    2 | 3
  2364.  */
  2365.  
  2366. typedef struct  {
  2367.     int x,y;
  2368. } point;
  2369.  
  2370. pointinpoly(pt,cnt,polypts)
  2371. point pt;       /* point to check */
  2372. int cnt;    /* number of points in poly */
  2373. point *polypts; /* array of points, */
  2374.         /* last edge from polypts[cnt-1] to polypts[0] */
  2375. {
  2376.     int oldquad,newquad;
  2377.     point thispt,lastpt;
  2378.     int a,b;
  2379.     int wind;       /* current winding number */
  2380.  
  2381.     wind = 0;
  2382.     lastpt = polypts[cnt-1];
  2383.     oldquad = whichquad(lastpt,pt); /* get starting angle */
  2384.     for(i=0;i<cnt;i++) { /* for each point in the polygon */
  2385.         thispt = polypts[i];
  2386.         newquad = whichquad(thispt,pt);
  2387.         if(oldquad!=newquad) { /* adjust wind */
  2388.             /*
  2389.              * use mod 4 comparisons to see if we have
  2390.              * advanced or backed up one quadrant
  2391.              */
  2392.             if(((oldquad+1)&3)==newquad) wind++;
  2393.             else if((((newquad+1)&3)==oldquad) wind--;
  2394.             else {
  2395.                 /*
  2396.                  * upper left to lower right, or
  2397.                  * upper right to lower left. Determine
  2398.                  * direction of winding  by intersection
  2399.                  *  with x==0.
  2400.                  */
  2401.                 a = lastpt.y - thispt.y;
  2402.                 a *= (pt.x - lastpt.x);
  2403.                 b = lastpt.x - thispt.x;
  2404.                 a += lastpt.y * b;
  2405.                 b *= pt.y;
  2406.  
  2407.                 if(a > b) wind += 2;
  2408.                 else wind -= 2;
  2409.             }
  2410.         }
  2411.         lastpt = thispt;
  2412.     }
  2413.     return(wind); /* non zero means point in poly */
  2414. }
  2415.  
  2416. /*
  2417.  * Figure out which quadrant pt is in with respect to orig
  2418.  */
  2419. int whichquad(pt,orig)
  2420. point pt;
  2421. point orig;
  2422. {
  2423.     if(pt.x < orig.x) {
  2424.         if(pt.y < orig.y) quad = 2;
  2425.         else quad = 1;
  2426.     } else {
  2427.         if(pt.y < orig.y) quad = 3;
  2428.         else quad = 0;
  2429.     }
  2430.     return ( quad ) ;    /* [I added the fix - EAH] */
  2431. }
  2432.  
  2433.  
  2434. Ken McElvain
  2435. decwrl!sci!kenm
  2436.  
  2437. -------------------------------------------------------------------------------
  2438.  
  2439. Computer Graphics Journals, by Juhana Kouhia (jk87377@tut.fi)
  2440.  
  2441. Here is a list, not as good as it could be.  I would like to see a short
  2442. descriptions about each journals on it.  I would like to see more information
  2443. about geometry related journals or journals that covers this newsgroup
  2444. subjects.  End of this list has list of journals, which was suggested to me,
  2445. but I didn't find enough information about them or I was too lazy to find
  2446. anything.  If somebody has suggestions what to do with them, please let me
  2447. know.
  2448.  
  2449. Additions, corrections, etc. are welcome to the list.  Thank you all who
  2450. helped me.
  2451.  
  2452.  
  2453. Computer Graphics, Geometry, Image Processing Journals
  2454. ======================================================
  2455.  
  2456. ACM Transactions On Graphics
  2457. ----------------------------
  2458.    -Quarterly
  2459.    -Available from:
  2460.     Association For Computing Machinery
  2461.     11 West 42 Street
  2462.     New York, NY 10036
  2463.     USA
  2464.  
  2465. Computer Aided Design
  2466. ---------------------
  2467.    -10 issues / year
  2468.    -Available from:
  2469.     Butterworth Scientific Ltd.
  2470.     88 Kingsway
  2471.     London WC2 6AB
  2472.     England
  2473.  
  2474. Computer Graphics
  2475. -----------------
  2476.    -Includes SIGGRAPH conference proceeding
  2477.    -Includes SIGGRAPH panel proceeding
  2478.    -Available from:
  2479.     Association For Computing Machinery
  2480.     11 West 42 Street
  2481.     New York, NY 10036
  2482.     USA
  2483.    -Also available from:
  2484.     Academic Press
  2485.  
  2486. Computer Graphics Forum
  2487. -----------------------
  2488.    -Journal of the European Association of Computer Graphics
  2489.     (EuroGraphics)
  2490.    -Available from:
  2491.     Elsevier Science Publishers B.V.
  2492.     Journals Department
  2493.     P.O. Box 211
  2494.     1000 AE Amsterdam
  2495.     The Netherlands
  2496.  
  2497. Computer Graphics World
  2498. -----------------------
  2499.    -Professional graphical application and industrial use
  2500.    -Monthly
  2501.    -Available from:
  2502.     PennWell Publishing Company
  2503.     119 Russell Street
  2504.     P.O. Box 457
  2505.     Littleton, Massachusetts 01460-0457
  2506.     USA
  2507.  
  2508. Computer Images International
  2509. -----------------------------
  2510.    -Professional graphical application and industrial use
  2511.    -Monthly
  2512.    -Available from:
  2513.     P.O. Box 109
  2514.     Maclaren House
  2515.     Scarbrook Road
  2516.     Croydon CR9 1QH
  2517.     England
  2518.     Phone: 01-688 7788
  2519.     Telex: 946665
  2520.     Fax:   01-681 1672
  2521.  
  2522. Computers & Graphics
  2523. --------------------
  2524.    -Available from:
  2525.     Oxword Books (GB)
  2526.  
  2527. Computer Vision, Graphics and Image Processing
  2528. ----------------------------------------------
  2529.    -Available from:
  2530.     Academic Press
  2531. ---> [split 1991]
  2532.  
  2533. Computer Vision, Graphics and Image Processing:
  2534.  Graphical Models and Image Processing
  2535. -----------------------------------------------
  2536.    -Available from:
  2537.     Academic Press
  2538.  
  2539. Computer Vision, Graphics and Image Processing:
  2540.  Image Understanding
  2541. -----------------------------------------------
  2542.    -Available from:
  2543.     Academic Press
  2544.  
  2545. Graphics Interface
  2546. ------------------
  2547.    -Proceedings of Canadian computer graphics convention
  2548.    -Available from in Canada:
  2549.     Canadian Information Processing Society
  2550.     243 College Street, 5th Floor
  2551.     Toronto, Ontario
  2552.     M5T 2Y1
  2553.     (416)-593-4040
  2554.    -Available from in USA:
  2555.     Morgan Kaufmann Publishers
  2556.     Order Fulfillment Center
  2557.     PO Box 50490
  2558.     Palo Alto, CA 94303
  2559.     USA
  2560.     (415)-965-4081
  2561.  
  2562. IEEE Computer Graphics & Applications
  2563. -------------------------------------
  2564.    -Monthly
  2565.    -Available from:
  2566.     IEEE Computer Society
  2567.     Circulation Department
  2568.     P.O. Box 3014
  2569.     Los Alamitos, CA 90720-9804
  2570.     USA
  2571.  
  2572. Image and Vision Computing
  2573. --------------------------
  2574.    -Image analysis
  2575.    -Available from:
  2576.     Butterworth Scientific Ltd.
  2577.     88 Kingsway
  2578.     London WC2 6AB
  2579.     England
  2580.  
  2581. Pixel
  2582. -----
  2583.    -Available from:
  2584.     Pixel Communications, Inc.
  2585.     245 Henry St., Suite 2-G
  2586.     Brooklyn, NY 11201
  2587.     USA
  2588.     Phone: (718) 624-3386
  2589.  
  2590. Signal Processing: Image Communication
  2591. --------------------------------------
  2592.    -A publication of the European Association for Signal Processing
  2593.     (EURASIP)
  2594.     EURASIP
  2595.     P.O. Box 134
  2596.     CH-1000 Lausanne 13
  2597.     Switzerland
  2598.    -Also available from:
  2599.     Elsevier Science Publishers B.V.
  2600.     Journals Department
  2601.     P.O. Box 211
  2602.     1000 AE Amsterdam
  2603.     The Netherlands
  2604.  
  2605. Visual Computer
  2606. ---------------
  2607.    -Available from:
  2608.     Springer-Verlag
  2609.     Heidelberger Platz 3
  2610.     D-1000 Berlin 33
  2611.     Germany
  2612.    -Also available from:
  2613.     Springer-Verlag New York, Inc.
  2614.     Journal Fulfillment Services, Dept. J
  2615.     P.O. Box 2485
  2616.     Secaucus, N.J. 07094
  2617.     USA
  2618.  
  2619. ******************************************************************************
  2620.  
  2621. Miscellaneous Journals
  2622. ======================
  2623.  
  2624. Leonardo
  2625. --------
  2626.    -Journal of the International Society for the Arts, Sciences &
  2627.     Technology
  2628.    -SIGGRAPH art show catalogue
  2629.    -Available from:
  2630.     Pergamon
  2631.  
  2632. ******************************************************************************
  2633.  
  2634. What?
  2635. =====
  2636.  
  2637. IEEE Trans. on Pattern Analysis and Machine Intelligence,
  2638.  
  2639. IEEE Trans. on Systems, Man, and Cybernetics
  2640.  
  2641. Journal of the Discrete and Computational Geometry
  2642.  
  2643. Machine Vision and Applications
  2644.  
  2645. Pattern Recognition
  2646.    -Available from:
  2647.     Pergamon
  2648.  
  2649. Pattern Recognition Letters
  2650.    -Available from:
  2651.     North-Holland
  2652.  
  2653. Symposium on Computational Geometry
  2654.  
  2655. Symposium on Foundation of CS
  2656.    -One or two papers a year on geometry
  2657.  
  2658. Symposium on Theory of Computing
  2659.  
  2660. -------------------------------------------------------------------------------
  2661. END OF RTNEWS
  2662.